Легко видеть, что если то есть общие проблемы поиска N P, которые не могут быть решены за полиномиальное время (создайте проблему общего поиска, имея как свидетелей для членства, так и свидетелей для не состоятельности).
Верно ли и обратное, т.е.
Означает ли существование общей задачи поиска не решаемой за полиномиальное время, N P ∩ c o N P ≠ P ?
Ответы:
Я предполагаю, что 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 .
источник
источник