781
1
0
19 октября
04:06
октябрь
2015

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

Соответственно, если существует такая задача, что для данного Х для любого Р(Х) при данном алгоритме количество шагов решения превышает Р(Х), это значит, что задача неразрешима за полиномиальное время (при помощи данного алгоритма).

2
0
Если вы знаете ответ на этот вопрос и можете аргументированно его обосновать, не стесняйтесь высказаться
Ответить самому
Выбрать эксперта