Определение на основе верификатора NP

Question

Я студент информатики, и у меня возникли проблемы с пониманием основанного на верификаторе определения проблем NP.

В определении сказано, что проблема в NP, если ее можно проверить за полиномиальное время с помощьюдетерминированная машина Тьюринга, получившая «сертификат».

Но что произойдет, если сертификат является именно решением проблемы?Это всего лишь немного, и оно явно полиномиально ограничено размером входного сигнала, и оно, очевидно, проверяется в постоянном, а следовательно, и полиномиальном времени.

Поэтому каждая проблема решения будет принадлежать НП.

Где я ошибаюсь?

Answer 1

Но что произойдет, если сертификат является именно решением проблемы?Это всего лишь немного, и оно явно полиномиально ограничено размером входного сигнала, и это, очевидно, проверяется в постоянном, таким образом, полиномиальном времени.

Почему «очевидно»?Возможно, вам придется потратить экспоненциальное количество времени на проверку решения, и в этом случае проблема не обязательно должна быть в NP.Дело в том, что, хотя сертификат является единственным битом для решения проблемы, вы не знаете , должен ли этот бит быть нулем или единицей для решения проблемы.(Если бы вы всегда знали это, то любая проблема решения в P или в NP была бы решаема в постоянное время.)

Answer 2

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

Следовательно, в большинстве случаеврешение проблемы - NP-Complete (например, чтобы найти, содержит ли набор городов тур), в то время как задачи оптимизации - NP-Hard (например, поиск минимальной длины тура)