Означает ли существование общей задачи поиска

13

Легко видеть, что если то есть общие проблемы поиска N P, которые не могут быть решены за полиномиальное время (создайте проблему общего поиска, имея как свидетелей для членства, так и свидетелей для не состоятельности).NPcoNPPNп

Верно ли и обратное, т.е.

Означает ли существование общей задачи поиска не решаемой за полиномиальное время, N Pc o N PP ?NпNPcoNпп

Кава
источник
Вы имеете в виду общую проблему поиска с проблемой решения NP? Является ли целочисленная факторизация такой проблемой?
Мухаммед Аль-Туркистани
2
Я думаю, что он имеет в виду TFNP.
domotorp

Ответы:

4

Я предполагаю, что P, NP и coNP в данном вопросе являются классами языков, а не классами проблем с обещаниями. Я использую то же соглашение в этом ответе. (На всякий случай, если вы говорите о классах проблем с обещаниями, то ответ утвердительный, потому что P = NP∩coNP как классы проблем с обещаниями эквивалентен P = NP.)

Тогда ответ отрицателен в релятивизированном мире.

Утверждение TFNP ⊆ FP известно как предложение Q в литературе [FFNR03]. Существует более слабое утверждение под названием Предложение Q ' [FFNR03], что каждое общее отношение NPMV с однобитовыми ответами находится в FP. (Здесь отношение с однобитовыми ответами означает подмножество {0,1} * × {0,1}.) Легко видеть, что предложение Q относительно какого-либо оракула подразумевает предложение Q 'относительно того же оракула.

Фортнау и Роджерс [FR02] рассмотрели отношения между утверждением P = NP∩coNP, предложением Q 'и несколькими другими связанными утверждениями в релятивизированных мирах. В частности, из теоремы 3.2 (или теоремы 3.3) в [FR02] следует, что существует оракул, относительно которого P = NP∩coNP, но предложение Q 'не выполняется (и, следовательно, предложение Q также не выполняется). Следовательно, в релятивизированном мире P = NP∩coNP не влечет предложение Q; или, принимая противоположность, существование отношения TFNP, которое не может быть вычислено за полиномиальное время, не подразумевает P ≠ NP∩coNP.

Ссылки

[FFNR03] Стивен А. Феннер, Лэнс Фортноу, Ашиш В. Найк и Джон Д. Роджерс. Инвертирование на функции. Information and Computing , 186 (1): 90–103, октябрь 2003 г. DOI: 10.1016 / S0890-5401 (03) 00119-6 .

[FR02] Лэнс Фортноу и Джон Д. Роджерс. Отделимость и односторонние функции. Вычислительная сложность , 11 (3–4): 137–157, июнь 2002 г. DOI: 10.1007 / s00037-002-0173-4 .

Цуёси Ито
источник
Спасибо, Цуёси. Существует также результат во второй версии проблемы, которая показывает, что ответ там доказуемо отрицателен: Пол Бим, Стивен А. Кук, Джефф Эдмондс, Рассел Импальяццо и Тонианн Питасси, « Относительная сложность проблем поиска NP », 1998
Каве
С:2N+12NС
@Kaveh: я не уверен, что понимаю ваш вопрос в комментарии. В нерелятивизированном мире единственный способ сказать, что «P = NP∩coNP» и «TFNP⊆FP» не эквивалентны, - это показать, что первое верно, а второе нет, если мы не докажем некоторую логическую независимость. результат. Но распространенное мнение состоит в том, что P ≠ NP∩coNP, что означает, что «P = NP∩coNP» и «TFNP⊆FP» эквивалентны (поскольку оба являются ложными). Поэтому я не знаю, какую гипотезу вы ищете.
Tsuyoshi Ito
TFNппNпсоNп
@Kaveh: Вы говорите о неэквивалентности между двумя предложениями «P = NP∩coNP» и «TFNP⊆FP», или о неэквивалентности между чем-то еще?
Цуёси Ито
5

Nпсо-Nп

domotorp
источник
TFUпFпNпсоNппTFNпFп
TFNпFпTFUпFп
Я не могу сказать, что МЫ не знаем, но я точно не знаю. Конечно, если мы допустим рандомизированные сокращения, то вы можете выполнить трюк Valiant-Vazirani, и последнее значение также станет верным. (Если я не ошибаюсь ...)
domotorp
FпTFUпTFNпFп
Да отлично.
Домоторп
Кажется, что Valiant-Vazirani здесь не работает (или, по крайней мере, я не понимаю, как это работает). Проблема заключается в том, что результатом является многообещающая проблема, например, SAT to USAT. Нам нужна не обещающая проблема. И, кажется, есть основания полагать, что эти два не должны быть равны. Я опубликую новый вопрос о TFNP и TFUP.
Каве