NP-полные комплекты сформированы из двух других наборов, только если хотя бы один NP-сложен?

Этот вопрос является чем-то вроде обратного к предыдущему вопросу о множествах, сформированных из операций над множествами на NP-полных наборах:

Если множество , являющееся результатом объединения, пересечения или декартового произведения двух разрешимых множеств и является NP-полным, является ли хотя бы один из обязательно NP-сложным? Я знаю, что они не могут быть оба в P (при условии, что P! = NP), так как P замкнут при этих операциях над множествами. Я также знаю, что условия «разрешимый» и «NP-жесткий» необходимы, поскольку, если мы рассмотрим любой NP-полный набор и другой набор вне NP (будь то NP-жесткий или неразрешимый), то мы можем сформировать два новых NP-hard устанавливает не в NP, чье пересечение является NP-полным. Например: и . Однако я не знаю, как действовать после этого. $L_1$ $L_2$ $L_1, L_2$ $L$ $B$ $L_1:= 01L \cup 11B$ $L_2:= 01L \cup 00B$

Я имею в виду , что в случае объединения не может быть правдой , так как мы можем принять NP-полный набор и выполнить строительство в теореме Ладнер, чтобы получить множество НПИ , который является подмножеством . Тогда является исходным NP-полным набором. Однако я не знаю, находится ли в NPI или NP-hard. Я даже не знаю, с чего начать для случая пересечения и декартового произведения. $A$ $B \in$ $A$ $B \cup (A \setminus B) = A$ $A \setminus B$

complexity-theory np-hard np np-intermediate Ari
источник

Проблема в P может быть NP-полной, если P = NP, что делает ваше утверждение «они оба не могут быть в P» ложным.

Wojowu

@Wojowu Спасибо, вы правы. Я просто предположил, что было понятно, что весь этот вопрос основан на предпосылке, что P! = NP. В противном случае это бессмысленно / тривиально, так как тогда у нас будет NPC = P. Я отредактирую вопрос.

Ари

@ Ari, На самом деле , даже если .

N P C \neq P

$NPC\not = P$

P = N P

$P=NP$

Том ван дер Занден

@TomvanderZanden Как это возможно? так что если P = NP, то любая проблема в NP может быть решена за полиномиальное время, включая проблемы в NPC.

N P C \subseteq N P

$NPC \subseteq NP$

Ари

@Ari Пустой набор и набор всех строк находятся в , но они не являются неполными. Вы ничего не можете уменьшить до пустого набора (или набора всех строк), потому что это всегда экземпляр no (соответственно yes).

N P

$NP$

N P

$NP$

Том ван дер Занден

Ответы:

Пересечение двух не-NP-сложных языков может быть NP-сложным. Пример: Решения любого экземпляра 3SAT - это заданное пересечение решений экземпляра HORN-3SAT и экземпляра ANTIHORN-3SAT. Это связано с тем, что предложение 3CNF должно быть предложением Horn или anti-Horn, а экземпляр 3SAT является соединением таких предложений. 3SAT конечно NP-завершен; HORN-3SAT и ANTIHORN-3SAT находятся в P.

Кайл Джонс
источник

Я не могу последовать вашему примеру. Пересечение HORN-SAT и ANTIHORN-SAT - довольно скучный язык, который определенно есть в P.

Yuval Filmus

HORN-3SAT можно определить разными способами. Одним из способов является исправление кодировки экземпляров HORN-3SAT - каждая строка кодирует некоторый такой экземпляр - и тогда HORN-3SAT состоит из выполнимых экземпляров. Эта кодировка, вероятно, отличается от кодировки, которую вы использовали бы для ANTIHORN-3SAT, поэтому неясно, что именно является языком пересечения - определенно не SAT.

Юваль Фильмус

Другой возможностью является определение HORN-3SAT как языка экземпляров 3SAT, которые (i) в форме рога, (ii) выполнимы. Теперь пересечение HORN-3SAT и ANTIHORN-3SAT имеет смысл: оно состоит из всех экземпляров 3SAT, которые (i) в форме рога и в антигорне, (ii) выполнимы. Это может быть проще, чем каждый из HORN-3SAT и ANTIHORN-3SAT.

Юваль Фильмус

Это очень странное определение пересечения языка, отличающееся от того, которое здесь подразумевалось. Если и являются языками (такими как 3SAT), под их пересечением мы подразумеваем .

L_{1}

$L_1$

L_{2}

$L_2$

L_{1} \cap L_{2}

$L_1 \cap L_2$

Юваль Фильмус

@ KyleJones @ Юваль Я думаю, что может быть некоторая путаница в отношении примеров против языков. Хотя каждый экземпляр 3SAT, безусловно, состоит исключительно из клаузул Horn и клаузул Anti-Horn, это не тот случай, когда язык равен или альтернативно поскольку эти наборы имеют экземпляры, каждый из которых состоит исключительно из предложений Horn или Anti-Horn, в то время как каждый экземпляр 3SAT может иметь смесь этих двух типов предложений.

3 S A T

$\mathsf{3SAT}$

H O R N 3 S A T \cap A N T I H O R N 3 S A T

$\mathsf{HORN3SAT}\cap\mathsf{ANTIHORN3SAT}$

H O R N 3 S A T \cup A N T I H O R N 3 S A T

$\mathsf{HORN3SAT}\cup\mathsf{ANTIHORN3SAT}$

Ari