Необходимо ли, чтобы проблемы NP были решением проблем?
Профессор Тим Рафгарден из Стэнфордского университета, преподавая MOOC, сказал, что решения проблем в классе NP должны быть полиномиальными по длине. Но статья в википедии говорит, что проблемы NP - это проблемы решения. Так какого типа проблемы в основном в классе NP? И нет ли необходимости говорить, что решения таких задач имеют вывод полиномиальной длины (поскольку задачи решения обязательно выводят либо 0, либо 1)?
3 ответа
Вероятно, он говорил о свидетелях и проверяющих.
Для каждой проблемы в NP существует верификатор - алгоритм чтения / машина Тьюринга - который может проверять утверждения "да" за полиномиальное время.
Идея в том, что у вас есть какая-то информация - свидетель, которая поможет вам сделать это, учитывая нехватку времени.
Например, в проблеме коммивояжера:
TSP = {(G, k) if G has a hamiltonian cycle of cost <= k}
Для заданного ввода (G, k) вам нужно только определить, находится ли проблемный экземпляр в TSP. Это ответ да / нет.
Теперь, если кто-то придет и скажет: этот экземпляр проблемы находится в TSP, вам потребуется доказательство. Тогда другой человек, вероятно, даст вам последовательность городов. Затем вы можете просто проверить, образуют ли города в этом порядке гамильтонов цикл, и равна ли общая стоимость цикла ≤ k.
Вы можете выполнить эту процедуру за полиномиальное время, учитывая, что свидетель имеет полиномиальную длину.
Используя эту последовательность городов, вы смогли правильно определить, что экземпляр проблемы действительно был в TSP.
Идея верификаторов заключается в том, что они берут объект / свидетель-доказатель полиномиальной длины, чтобы проверить за полиномиальное время, что определенный экземпляр проблемы находится в языке.
Стандартное определение NP состоит в том, что это только класс проблем решения. Проблемы с решением всегда дают ответ "да / нет" и, следовательно, имеют постоянный размер.
Я не смотрел видео / курс, но, думаю, он говорил о сертификатах / проверках, а не о решениях. Большая разница.