Существует ли задача, которая разрешима за полиномиальное время, но не поддается проверке за полиномиальное время?

Мой коллега и я только что нажали несколько заметок одного из наших профессоров. В примечаниях говорится, что есть задачи, которые можно решить за полиномиальное время (относятся к классу PF), но которые НЕ поддаются проверке за полиномиальное время (НЕ относятся к классу NPF).

Чтобы уточнить эти классы: мы получаем некоторый вход X и производим некоторый выход Y такой, что (X, Y) находятся в отношении R, представляющем нашу задачу. Если за полиномиальное время можно получить Y для X, задача относится к классу PF. Если возможно проверить сертификат Z полиномиальной длины, который доказывает, что кортеж (X, Y) находится в отношении R за полиномиальное время, задача относится к классу NPF.

Мы не говорим о проблемах решения, где ответом является просто ДА или НЕТ (более формально, если некоторая строка принадлежит какому-либо языку). Для решения проблем кажется, что PF является подходящим подмножеством NPF. Однако для других задач все может быть иначе.

Знаете ли вы о задаче, которая может быть решена за полиномиальное время, но не проверена за полиномиальное время?

complexity-theory np Drozi
источник

Возможно, я неправильно понимаю, но почему следующий алгоритм проверки не является полиномиальным? Учитывая

, вычислите функцию

самостоятельно, используя алгоритм полиномиального времени, и верните «исправить», если

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

(x, y)

$(x,y)$

f (x)

$f(x)$

f (x) = y

$f(x)=y$

Lieuwe Vinkhuijzen

@LieuweVinkhuijzen "сказать, что есть проблемы, поддающиеся проверке за полиномиальное время, но не решаемые за полиномиальное время?" [см. необходимо]

Т. Веррон

@ T.Verron Хаха, я тоже был бы очень рад увидеть доказательства профессора в этом утверждении;)

Lieuwe Vinkhuijzen

Ответы:

Это возможно только при наличии множества допустимых выходов для данного входа. Т.е. когда отношение не является функцией, потому что оно нарушает единственность. $R$

Например, рассмотрим эту проблему:

Учитывая (представленный в унарном виде) и TM , создайте другой TM такой, что и (где обозначает кодирование (число Геделя) в натуральное число) $n \in \mathbb{N}$ $M$ $N$ $L(M)=L(N)$ $\# N > n$ $\# N$ $N$

Решение этой проблемы тривиально: продолжайте добавлять несколько избыточных состояний к TM , возможно, с некоторыми фиктивными переходами между ними, пока его кодировка не превысит . Это базовое повторное применение леммы Паддинга к ТМ. Это потребует дополнений, каждое из которых может добавить одно состояние, следовательно, это может быть сделано за полиномиальное время. $M$ $n$ $n$

С другой стороны, с учетом является неразрешимым , чтобы проверить , если является правильным выходом для входов . Действительно, проверка неразрешима (примените теорему Райса), и ограничение отбрасывает только конечное число s из них. Поскольку мы удаляем конечное количество элементов из неразрешимой проблемы, мы все равно получаем неразрешимую проблему. $n,M,N$ $N$ $n,M$ $L(M)=L(N)$ $\#N > n$ $N$

Вы также можете заменить неразрешимое свойство чтобы получить вариации, которые все еще вычислимы, но NP сложны / полны. Например, учитывая (в унарном порядке), тривиально вычислить граф имеющий клик внутри. Но с учетом трудно проверить, существует ли клик. $L(M)=L(N)$ $n$ $G$ $n$ $n,G$ $n$

чи
источник

Ожидается, что это не так. Отличный ответ!

Филип Хаглунд

Это не отвечает на вопрос. ОП специально задала вопрос о проблеме, которую нельзя проверить в обычном смысле, когда в дополнение к вводу и предполагаемому ответу мы получаем сертификат

который подтверждает правильность ответа. В вашем случае сертификат - это биты, используемые для недетерминированной генерации новой эквивалентной машины Тьюринга. Учитывая

, то легко проверить , является ли

дает машину

. Без

вопрос заключается в том, легко ли создавать жесткие экземпляры языков (NPC), что справедливо только для Minicrypt и Cryptomania.

z

$z$

M, N

$M, N$

z

$z$

z

$z$

M

$M$

z

$z$

Lieuwe Vinkhuijzen

@chi Не все пары

могут быть сертифицированы, но набор пар

сгенерированных вашим алгоритмом, может быть сертифицирован. Сертификат является расшифровкой вашего алгоритма, создающего

из

(например, «начните с

, затем добавьте это состояние и добавьте этот переход, затем ... и вуаля,

!»). В общем, если

является недетерминированным алгоритмом, который, учитывая

, всегда вычисляет допустимый

, то расшифровка стенда пути вычисления

является свидетельством того, что данный

допустим.

M, N

$M, N$

M, N

$M, N$

N

$N$

M

$M$

M

$M$

N

$N$

T

$T$

x

$x$

y

$y$

T (x)

$T(x)$

y

$y$

Lieuwe Vinkhuijzen

@chi В этом вопросе есть небольшой нюанс: для произвольного отношения

возможно, что не все допустимые

являются сертифицируемыми, и вы привели элегантный пример. Однако, вопрос не спрашивает , является ли допустимым , но uncertifiable отношения существуют (ответ да , на вашем примере), вместо этого он спрашивает , может ли у нас есть алгоритм , который производит допустимый, uncertifiable выход. Ответ здесь, должно быть, нет , из-за аргумента выше.

R

$R$

y

$y$

Lieuwe Vinkhuijzen

$NP\subsetneq P$

Это всего лишь проработка первого предложения ответа @ chi, так как я не нашел его очевидным.

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

Ранее вы доказали (математически), что вывод алгоритма является решением проблемы, и в этом случае сами шаги алгоритма образуют доказательство правильности.
У вас есть другой алгоритм для проверки того, что вывод действительно является решением, и в этом случае вы должны запустить этот алгоритм (в противном случае вы попали бы в случай № 1), что подразумевает, что вы делаете это за полиномиальное время.

Поэтому такой проблемы быть не может.

Mehrdad
источник

Я не понимаю # 2. Что означает, что другой алгоритм выполняется за полиномиальное время?

Альберт Хендрикс

@AlbertHendriks: Если верификатор не выполнялся за полиномиальное время, то исходный решатель не мог утверждать, что нашел правильное решение за полиномиальное время, потому что ему нужно запустить верификатор, чтобы убедиться, что его решение корректно.

Мердад