Czy kompletne zestawy NP są tworzone z dwóch innych zestawów tylko wtedy, gdy co najmniej jeden jest twardy NP?

To pytanie jest nieco odwrotne do poprzedniego pytania dotyczącego zestawów utworzonych z operacji na zestawach na zestawach NP-complete:

Jeśli zbiór wynikający ze związku, przecięcia lub iloczynu kartezjańskiego dwóch rozstrzygalnych zbiorów $L_1$ i jest NP-kompletny, to czy przynajmniej jeden z koniecznie NP-twardy? Wiem, że oba nie mogą być w P (zakładając, że P! = NP), ponieważ P jest zamknięte w ramach tych ustawionych operacji. Wiem również, że warunki „rozstrzygalnego” i „NP-twardego” są konieczne, ponieważ jeśli weźmiemy pod uwagę jakikolwiek NP-kompletny zestaw i inny zestaw poza NP (czy to po prostu NP-twardy, czy nierozstrzygalny), możemy utworzyć dwa Zestawy twarde NP nie w NP, których przecięcie jest NP-kompletne. Na przykład: , a $L_2$ $L_1, L_2$ $L$ $B$ $L_1:= 01L \cup 11B$ $L_2:= 01L \cup 00B$ . Nie wiem jednak, jak to zrobić.

Myślę, że sprawa jedności nie może być prawdą, ponieważ możemy podjąć NP-kompletny zestaw i przeprowadzić budowę w LADNER Twierdzenie dostać zestaw NPI, który jest podzbiorem . Zatem jest oryginalnym kompletem NP-kompletnym. Nie wiem jednak, czy nadal jest w NPI czy NP-trudny. Nie wiem nawet, od czego zacząć w przypadku skrzyżowania i produktu kartezjańskiego. $A$ $B \in$ $A$ $B \cup (A \setminus B) = A$ $A \setminus B$

complexity-theory np-hard np np-intermediate Ari
źródło

Problem w P może być NP-zupełny, jeśli P = NP, co powoduje, że twoje twierdzenie „nie mogą być w P” fałszywe.

Wojowu

@Wojowu Dziękuję, masz rację. Po prostu założyłem, że zrozumiano, że całe to pytanie opiera się na założeniu, że P! = NP. W przeciwnym razie jest to bez znaczenia / trywialne, ponieważ mielibyśmy wtedy NPC = P. Przeredaguję pytanie.

Ari

@Ari, faktycznie

, nawet jeśli

N P C \neq P

$NPC\not = P$

P = N P

$P=NP$

Tom van der Zanden

@TomvanderZanden Jak to możliwe?

więc jeśli P = NP, to każdy problem w NP można rozwiązać w czasie wielomianowym, w tym problemy w NPC.

N P C \subseteq N P

$NPC \subseteq NP$

Ari

@Ari zbiór pusty i zbiór wszystkich ciągów są w

, ale nie są one

-Complete. Nie można zredukować niczego do pustego zestawu (lub zestawu wszystkich ciągów), ponieważ zawsze jest to instancja typu „nie” (lub „tak”).

N P

$NP$

N P

$NP$

Tom van der Zanden

Odpowiedzi:

Przecięcie dwóch języków nie-NP-trudnych może być NP-trudne. Przykład: Rozwiązania dowolnej instancji 3SAT stanowią ustawione skrzyżowanie rozwiązań instancji HORN-3SAT i instancji ANTIHORN-3SAT. Wynika to z faktu, że klauzula 3CNF musi być klauzulą Horn lub anti-Horn, a instancja 3SAT jest koniunkcją takich klauzul. 3SAT jest oczywiście NP-zupełny; HORN-3SAT i ANTIHORN-3SAT znajdują się w P.

Kyle Jones
źródło

Nie mogę pójść za twoim przykładem. Przecięcie HORN-SAT i ANTIHORN-SAT jest dość nudnym językiem, który zdecydowanie jest w P.

Yuval Filmus

HORN-3SAT można zdefiniować na wiele sposobów. Jednym ze sposobów jest poprawienie kodowania instancji HORN-3SAT - każdy ciąg koduje niektóre takie instancje - a następnie HORN-3SAT składa się z zadowalających instancji. To kodowanie prawdopodobnie różni się od kodowania, którego użyłbyś do ANTIHORN-3SAT, więc nie jest jasne, jaki dokładnie jest język skrzyżowania - zdecydowanie nie SAT.

Yuval Filmus,

Inną możliwością jest zdefiniowanie HORN-3SAT jako języka instancji 3SAT, które są (i) w postaci rogu, (ii) zadowalające. Teraz przecięcie HORN-3SAT i ANTIHORN-3SAT ma sens: składa się ze wszystkich instancji 3SAT, które są (i) zarówno w postaci Rogu, jak i przeciw Rogowi, (ii) zadowalające. Może to być łatwiejsze niż w przypadku każdego z HORN-3SAT i ANTIHORN-3SAT.

Yuval Filmus,

Jest to bardzo dziwna definicja przecięcia języka, inna niż ta, która miała tu na myśli. Jeśli

są językami (np. 3SAT), przez ich przecięcie rozumiemy

L_{1}

$L_1$

L_{2}

$L_2$

L_{1} \cap L_{2}

$L_1 \cap L_2$

Yuval Filmus,

@ KyleJones @ Yuval Myślę, że mogą wystąpić pewne nieporozumienia dotyczące instancji a języków. Podczas gdy każdy przykład z 3SAT pewnością składa się wyłącznie z klauzul Horn i klauzul przeciw rogu, to jest nie tak, że język

równa

lub alternatywnie

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}$

ponieważ zestawy te mają instancje złożonewyłączniez klauzul Horn lub klauzul Anti-Horn, podczas gdy każde wystąpienie 3SAT może zawierać mieszankę tych dwóch typów klauzul ..

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