к Оглавлению
4. или 2.1+ Данная задача будет из класса P+, если есть алгоритм M(x), который в пределах полиномиального от |x| и S(x) времени (т.е. количество шагов работы алгоритма M(x) – в пределах p(|x|, S(x)) где S(x) работает полиномиальное время от размера |x|) возвращает:
y, если имеется y, такой что L(x, y) = 1 и в т.ч. |y| ≤ S(x),
0, если такого y нет.
Разумеется, если алгоритм проверки имеет вид L(t, S, y), то соответствующий ему алгоритм из P+ будет иметь вид M(t, S).
И пункт 4 (2.1+) превращается в п.2.1, если S(x) = p_2(|x|). А задача из класса P+ оказывается тогда задачей из класса P.
5. (Не)полиномиальность времени работы алгоритма никак не зависит от того, сколько времени данный алгоритм работает на данной единичной задаче – если время его работы конечно.
Действительно, любая единичная задача, которая решается за конечное время, может считаться решенной за полиномиальное время. Ведь полиномиальность времени решения относится лишь к массовой задаче, и если единственная задача (или конечное их число) из данной массовой задачи решается за огромное, но конечное время, то к полиному просто добавляется какая-то константа. Поэтому корректный алгоритм-решение M(x) может работать сколь угодно долго над решением единичной задачи L(x, y) (при заданном x). Но если он всё же остановится с корректным результатом – то его долгая работа никак не уменьшит возможности найти полиномиальное решение для массовой задачи данного L(x, y) (при произвольном аргументе x).
