Насколько я понимаю, полиномиальное время - это термин для оценки сложности решения задачи при помощи определенного алгоритма для работы с машиной Тюринга и ей подобными моделями. Суть в следующем: пусть у нас есть задача размерностью Х (это значит, что суммарное число уравнений и параметров, определяющих эту задачу, равно Х) и некоторый алгоритм ее решения, тогда полиномиальное время означает, что при помощи данного алгоритма на машине Тюринга данная задача будет решена не более, чем за Р(Х) шагов. Где Р(Х) - это какой-то определенный для данного алгормитма полином.
Соответственно, если существует такая задача, что для данного Х для любого Р(Х) при данном алгоритме количество шагов решения превышает Р(Х), это значит, что задача неразрешима за полиномиальное время (при помощи данного алгоритма).