В классе сложности P принимает = решает. Почему не нп?

Question

Предположим, что некоторая проблема L находится в классе сложности P. Тогда есть некоторый алгоритм A полиномиального времени, который решает проблему. У нас есть следующая теорема: если A принимает L, то A решает L.

Доказательство работает, отмечая, что если A выполняется за полиномиальное время, то существуют некоторые неотрицательные константы c, k, такие что время выполнения A равно cn^k, где n - размер входного L. Таким образом, мы можем построить многочлен алгоритм времени A', который вызывает A и возвращает 1, если A возвращает 1 за время<= cn^k, и возвращает 0, если A требуется больше времени, чем cn^k, чтобы вернуть что-то. Делая это, мы отмечаем, что если A пытается войти в бесконечный цикл, то A'просто останавливает процесс за много времени и возвращает 0, что означает, что A' отклоняет комплимент L.

Мой вопрос: почему это доказательство не работает для класса сложности NP? Разве мы не можем просто сказать, что если L находится в NP, то существует недетерминированный многовидовой алгоритм A, который решает L, поэтому просто определите A', как указано выше?

Answer 1

"Решение" проблемы означает возможность сказать, есть ли данная строка в языке. Если строка не на языке NP, нет полиномиального периода времени, в течение которого вы можете ждать, пока не произойдет сбой принятия, прежде чем объявить, что строка не на языке, что делает ваш алгоритм несостоятельным.

Для языков в P вы не знаете, что такое "полиномиальное количество времени" на самом деле, но вы знаете, что ваш алгоритм завершится за определенное время для любого ввода. Но для NP тестирование входных данных не на языке может не прекратиться никогда, поэтому вы никогда не сможете определить, не введены ли входные данные на языке или вы просто не ждали достаточно долго.