Вы уж для тупого объясните. Например, где в Вашей конструкции "для школьников" полиномиальность?
Вообще ИМХО проблема недостаточно четко поставлена.
разных "полиномиальностей" сложности, трудности, врямязатратности (наверно о ресурсоемкости надо говорить, а не о сложности, так как сложность подразумевает ум решателя) вычислений (численных реализаций решений) в разных книгах разные встречаются, причем многие книги - учебники
Вот пример, кто-то вычисляет для графов (так задача формализована) число граней. Если решать просто просмотром с проверками, то программа, так сказать, реализует алгоритм с явно экспоненциальной сложностью, но если знать формулу Эйлера, то у алгоритма явно линейная сложность, как бы эту сложность кто не определял.
И о каких вечных истинах (чистых истинах, чем занимается математика) идет речь? То есть P может быть всего лишь какой-то оценкой технических устройств,
но едва ли алгоритмов и тем более самих задач. имхо
Такая же ситуация и, например, в программировании (а пример уместный,
так как у Кука в его размышлениях фигурируют машина Тьюринга, формальные языки и т.п.) - то есть один и тот же алгоритм разные программеры могут реализовывать по-разному, даже если оценивать сложность глуповато количеством строчек, один напишет 10 строк, а другой несколько тысяч строк. Можно говорить, что первый использует уже написанные и отлаженные библиотеки, но это не намного
изменит всей ситуации, так как даже когда все будут писать на ассемблерах
и вроде труд и сложность можно измерять количеством строк программы, то и в этом случае более сообразительный программист напишет более лучшую программу (хотя вообще-то более умная ПРАВИЛЬНАЯ, то есть
полноценно решающая задачу, как правило более короткая, чем другая менее интеллектуальная ТОЖЕ ПРАВИЛЬНАЯ программа).
