Означает ли coNP-полнота NP-твердость?

12

Означает ли coNP-полнота NP-твердость? В частности, у меня есть проблема, которую я показал как coNP-полная. Могу ли я утверждать, что это NP-жесткий? Я понимаю, что могу требовать твердости coNP, но я не уверен, является ли эта терминология стандартной.

Я согласен с утверждением, что если NP-полная проблема принадлежит coNP, то NP = coNP. Тем не менее, в этих заметках говорится, что если NP-сложная задача относится к coNP, то NP = coNP. Тогда это может означать, что я не могу утверждать, что моя проблема сложна с точки зрения NP (или что я доказал, что coNP = NP, в чем я сильно сомневаюсь).

Возможно, что-то не так с моим мышлением. Я думаю, что проблема, связанная с coNP, является NP-трудной, потому что:

  1. каждая проблема в NP может быть сведена к ее дополнению, которое будет принадлежать coNP.
  2. проблема комплемента в coNP сводится к моей проблеме полного coNP.
  3. таким образом, у нас есть сокращение от каждой проблемы в NP до моего coNP-полного, так что моя проблема - NP-сложная.
complexity-theory np-hard Остин Бьюкенен
источник
Одним словом, нет! по крайней мере, на основе текущих знаний. вопрос тесно связан с P =? NP (или, точнее, coNP =? NP, который также открыт). отметим, что если доказано, что coNP ≠ NP, то P ≠ NP также доказано, потому что P замкнуто относительно дополнения.
2013 года

Ответы:

10

Вы утверждаете, что каждая проблема в NP может быть сведена к ее дополнению , и это верно для сокращений Тьюринга, но (вероятно) не для сокращений многие-один. Многократное сокращение от до является функцией временного числа такой что для всех , если .L 2 f x x ∈ L 1 f ( x ) ∈ L 2L1L2fxx∈L1f(x)∈L2

Если какая - то проблема в CONP была NP-трудной, то для любого языка было бы функция полиномиальной такое , что для всех , тогда и только тогда . Поскольку находится в coNP, это дает алгоритм coNP для , показывающий, что NP coNP и, таким образом, NP coNP. Большинство исследователей не ожидают, что это так, и поэтому проблемы в coNP, вероятно, не являются NP-сложными.M ∈ N P f x x ∈ M f ( x ) ∈ L L M ⊆ =LM∈NPfxx∈Mf(x)∈LLM⊆=

Причина, по которой мы используем сокращения Карпа, а не сокращения Тьюринга, заключается в том, что мы можем различать проблемы NP-hard и coNP-hard. См. Этот ответ для более подробной информации (сокращения Тьюринга в этом ответе называются сокращениями Кука).

Наконец, coNP-hard и coNP-complete являются стандартной терминологией, и вы можете использовать их.

Юваль Фильмус
источник
«но не для много-одного сокращения» - не проблема решения точно , что мы не знаем , есть ли Karp-сокращение от а ( со ) НП -Language к его дополнению? NP=?coNPcoNP
Г. Бах
Это правильно, и это также то, что я показываю в ответе. Когда я заявил, что это не верно для сокращений «многие-один», я имел в виду не это в строго логическом смысле, а скорее в том смысле, что «сокращение, о котором вы думаете, является сокращением по Тьюрингу, но не сокращением многие-один» ,
Юваль Фильмус
О, хорошо, да, это, вероятно, проблема.
Г. Бах
Благодарю. Какая хорошая ссылка для этого? В частности, для «NP = coNP при сокращениях Кука, но считается, что они отличаются от сокращений Карпа»?
Остин Бьюкенен
Вера в то, что NP отличается от coNP, довольно широко распространена. Иногда это приписывают Стивену Кук. То, что NP-твердость такая же, как и CoNP-твердость при сокращениях Кука, немедленно следует из определения.
Юваль Фильмус
6

x∈LMx∉L¯MxNP

NPcoNPL∈coNPM

x∈L⟺∀z∈{0,1}p(|x|):M(x,z)=1

L¯M'

x∈L¯⟺∃z∈{0,1}q(|x|):M'(x,z)=1

NPM'KcoNPMK∀coNPNPM'0x∈K∃∀

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

Г. Бах
источник
4
Удивительно, однако, что известно, что NL = coNL, NPSPACE = coNPSPACE, и в целом недетерминированные классы, определенные ограничениями пространства, закрываются при дополнении. Это теорема Иммермана-Селецкого.
Юваль Фильмус
Интересно, я этого не знал - но интуиция, стоящая за этим, вероятно, такова, как всегда с космическими классами: мы можем просто повторно использовать пространство.
Г. Бах
stlog⁡nst