Существуют ли проблемы, которые легко вычислить, но трудно проверить?

Предполагая, что P NP, NP-полные проблемы «трудно решить, но есть ответы, которые легко проверить». Имеет ли смысл рассматривать противоположные, то есть проблемы, для которых легко вычислить правильный ответ, но трудно проверить произвольное предполагаемое решение? $\neq$

Я думаю, что такая проблема подразумевает либо:

Экспоненциально много «правильных» ответов для любого заданного входа, потому что в противном случае проверка может быть проведена простым вычислением всех правильных ответов.
Некоторые «правильные» ответы легко вычислить, а другие трудно найти.

complexity-theory rphv
источник

Я сомневаюсь в этом. Если ответ легко вычислить, выбор сертификата прост: предоставьте предполагаемый ответ с проблемой и «проверьте» ответ, решив проблему, и выясните, действительно ли предполагаемый ответ является ответом.

Patrick87

@ Patrick87 - Я думаю, что обратился к этому вопросу. Как насчет многозначной функции

которая связывает набор значений

со входом

? Предположим, что

и что легко выбрать элемент из

, но, учитывая

, трудно определить, является ли

f

$f$

I_{f} (x) = {y_{1}, y_{2}, \dots}

$I_f(x) = \{y_1, y_2, \dots \}$

x

$x$

| I_{f} (x) | = 2^{| x |}

$|I_f(x)| = 2^{|x|}$

I_{f} (x)

$I_f(x)$

z

$z$

z \in I_{f} (x)

$z \in I_f(x)$

rphv

@ Patrick87 Решатель может быть детерминированным и выводить только один из всех существующих ответов. Затем вам нужен эффективный способ проверить, эквивалентны ли два решения. Может ли эквивалентность на множестве быть сложнее, чем решить проблему на нем?

Рафаэль

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

Patrick87

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

Жиль "ТАК ... перестать быть злым"

Ответы:

Если у вас все в порядке с искусственными проблемами, вы можете их решить. Вот несколько из них:

Если дано положительное целое число n в унарном порядке, ответьте на выполнимую формулу 3CNF для n булевых переменных.
Дать одну выполнимую формулу 3CNF легко, но решить, является ли данная формула 3CNF выполнимой или нет, является 3SAT, хорошо известной NP-полной задачей.
Там нет ввода. Просто ответьте на машину Тьюринга, которая останавливается (при запуске с пустой входной лентой).
Дать одну такую машину Тьюринга легко, но не решается, останавливается ли данная машина Тьюринга или нет.

Добавлено : Кстати, я не думаю, что то, что вы написали в последнем абзаце, содержит:

Я думаю, что такая проблема подразумевает экспоненциально много «правильных» ответов для любого заданного входного значения, потому что в противном случае проверка может быть выполнена простым вычислением всех правильных ответов.

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

Имея машину Тьюринга M , ответьте на одно из следующих утверждений: « M останавливается на пустой входной ленте», « M не останавливается на пустой входной ленте» и « M - машина Тьюринга».
Дать одно решение легко : вы всегда можете выбрать « М - машина Тьюринга». Однако, является ли данный ответ правильным или нет, невозможно решить. Обратите внимание, что в этой проблеме есть только два решения для каждого экземпляра.

Цуёси Ито
источник

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

Жиль, ТАК - прекрати быть злым »

@ Жиль: Нет, я так не думаю. Я назвал эти проблемы «искусственными», потому что очень маловероятно, что кто-то сначала столкнется с этими проблемами, а потом узнает, что легко дать один ответ и трудно определить правильность данного кандидата ответа. Но эта «искусственность» отнюдь не является строгим понятием.

Tsuyoshi Ito

@ Tsuyoshi Ito - Спасибо за четкий ответ. Я отредактировал последний абзац, чтобы отразить ваше понимание.

rphv

Хотя ответ Цуёси Ито охватывает «основной» ответ, я хотел добавить две тонкие заметки.

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

Как пример подобного рода проблемы, проблема Дойча-Йоссы немного страдает от этого. Если оракул не является сбалансированной функцией, тогда квантовый компьютер может быстро определить, что это так, но нет коротких доказательств, которые позволили бы классическому компьютеру проверить это. (Это только «похожая» проблема, потому что она все еще может быть проверена другим квантовым компьютером, и проверка также выполняется в классическом BPP, даже если она не в P.)

Алекс Мейбург
источник