Нужно ли для проблем с NP решать проблемы?

Question

Профессор Тим Руггарден из Стэнфордского университета во время обучения MOOC сказал, что решения задач в классе NP должны быть многочленными по длине. Но wikipedia article говорит, что проблемы NP - это проблемы с решением. Итак, какие проблемы возникают в основном в классе NP? И не нужно ли говорить, что решения таких проблем имеют выход полиномиальной длины (поскольку проблемы решения обязательно выводят либо 0, либо 1)?

Answer 1

Он, вероятно, говорил о свидетелях и верификаторах.

Для каждой проблемы в NP существует верификатор — читаемый алгоритм/машина turing —, которая может проверять «да» -заложения в полиномиальное время.

Идея состоит в том, что у вас есть какая-то информация — свидетель —, чтобы помочь вам сделать это с учетом ограничений по времени.

Например, в задачи коммивояжера:

TSP = {(G, k) if G has a hamiltonian cycle of cost <= k} 

Для данного входа (G, K), вам нужно только определить, является ли экземпляр проблема заключается в TSP. Это ответ «да/нет».

Теперь, если кто-то приходит и говорит: Эта проблема возникает в TSP, вы потребуете доказательства. Тогда другой человек, вероятно, даст вам последовательность городов. Затем вы можете просто проверить, являются ли города в этом порядке гамильтоновым циклом и равна ли общая стоимость цикла ≤ k.

Вы можете выполнить эту процедуру в полиномиальное время —, учитывая, что свидетель является полиномиальным по длине.

Используя эту последовательность городов, вы смогли правильно определить, что экземпляр проблемы действительно находился в TSP.

Это идея верификаторов: они берут объект доказательства/свидетеля, который является полиномиальным по длине, чтобы проверять полиномиальное время, что в языке есть определенный экземпляр проблемы.

Answer 2

Стандартное определение NP заключается в том, что это только класс решений. Проблемы с решением всегда дают ответ «да/нет» и, следовательно, имеют выходной сигнал постоянного размера.

Answer 3

sDidn't смотреть видео/курс, но я предполагаю, что он говорил о сертификатах/проверке, а не о решениях. Большая разница.