Jakie są złożoności następujących podzbiorów SAT?

Załóżmy, że $P \neq NP$

Do tetracji użyj następującego zapisu (tj. ). ${}^ia$ ${}^ia = \underbrace{a^{a^{\cdot^{\cdot^{\cdot^{a}}}}}}_{i \mbox{ times}}$

| x | jest wielkością instancji x.

Niech L będzie językiem, $L|_{f(i)\leq |x| < g(i)} := \{ x \in L \mbox{ | } \exists i \in \mathbb{N}\mbox{, } f(i) \leq |x| < g(i) \}$

Jaka jest złożoność następujących języków:

$L_1 = SAT|_{{}^{2i}2 \leq |x| < {}^{2i+1}2}$ $L_2 = SAT|_{{}^{2i+1}2 \leq |x| < {}^{2i+2}2}$

Ponieważ , nie mogą być oba w P przy założeniu, że . Ponieważ oba mają dziury wykładnicze, nie sądzę, że SAT można zredukować do jednego. $L_1 \sqcup L_2 = SAT$ $P \neq NP$

Stąd intuicja byłaby taka, że oba są w NPI, ale nie mogę znaleźć dowodu ani dyskomfortu.

Dwa inne języki to $L_3 = SAT|_{|x|={}^{2i+1}2}$ $L_4 = SAT|_{|x|={}^{2i}2}$

Jeśli jedno z nich jest w NPC, drugie jest w P, ponieważ dla każdej instancji jednej nie można przekształcić w większą instancję drugiej, ponieważ ma wielkość wykładniczą, a mniejsze instancje mają wielkość logarytmiczną. Wciąż z intuicji nie ma powodu, dla którego mieliby inną złożoność. Jaka byłaby ich złożoność?

Dowód Ladnera na problemy NPI przy założeniu, że używa języków takich jak lub , ale i nie są budowane przez przekątną. $P \neq NP$ $L_1$ $L_2$ $L_1$ $L_2$

cc.complexity-theory np-hardness complexity-classes Ludovic Patey
źródło

W waszych językach jest wiele wystąpień uzupełnionych przez dodanie dodatkowych klauzul, które nie wchodzą ze sobą w interakcje. Wydają się zatem NPI według argumentu diagonalizacji Schöninga? dx.doi.org/10.1016/0304-3975(82)90114-1

András Salamon

Po „nie mogą być oba w P”, należy powiedzieć „przy założeniu, że P NP ...”

\neq

$\ne$

Emil

Dodałem „przy założeniu”, nawet jeśli już założyłem to założenie wcześniej.

Ludovic Patey,

Jeśli L1 lub L2 jest zakończone NP, wówczas hipoteza izomorfizmu zawodzi, ponieważ ani L1, ani L2 nie jest cylindrem (ma funkcję wypełniania). Udowodnienie, że jeden z nich jest NP-zupełny, wymaga technik nierelatywizujących. Nie widzę jednak żadnych przeszkód, aby pokazać, że jeden z nich nie jest NP-kompletny.

Joshua Grochow

Być może byłem trochę niejasny z moimi kwantyfikatorami. Dodajmy nawiasy: nie istnieje maszyna wyroczni taka, że [dla wszystkich [ rozwiązuje ]]. Oznacza to, że dla każdego , może się okazać, że za jakiś X, rozwiązuje jeden z języków, ale to nie może być prawdziwe dla wszystkich . Na przykład bez wyroczni może rozwiązać (nierelatywizowany), ale bez względu na to, co to jest , będzie taka wyrocznia, że nie rozwiąże żadnego języka.

M

$M$

X

$X$

M^{X}

$M^X$

L_{1}^{X} o r L_{2}^{X}

$L_1^X or L_2^X$

M

$M$

M^{X}

$M^X$

X

$X$

M

$M$

L_{1}

$L_1$

M

$M$

Joshua Grochow

Odpowiedzi:

Myślę, że oba są NPI przy silniejszym założeniu (ale oczywiście prawdzie), że NP nie ma „nieskończenie często P” - tj. Każdy algorytm wielomianowy A i każdy wystarczająco duży n, A nie rozwiązuje SAT na wejściach o długości n.

W takim przypadku takich języków nie ma w P, ale nie mogą one być NP kompletne, ponieważ w przeciwnym razie redukcja z SAT do języka L z dużymi dziurami da algorytm SAT, który odniesie sukces w tych dziurach.

Takie założenie jest również konieczne, ponieważ w przeciwnym razie języki mogą być w P lub NP-zupełne, w zależności od tego, gdzie znajdują się „łatwe długości wejściowe”.

Boaz Barak
źródło

@Boaz: Rozumiem, co masz na myśli mówiąc, że „takie założenie jest konieczne”, ale mam problem z sformalizowaniem konieczności. Wydaje mi się, że jeden konstruuje wyrocznię

, bez większych trudności, tak że

, istnieje wieloczynnikowa maszyna

taka, że

decyduje

na nieskończenie wielu długościach wejściowych, ale

są

-intermediate.

X

$X$

P^{X} \neq N P^{X}

$P^X \neq NP^X$

M

$M$

M^{X}

$M^X$

S A T^{X}

$SAT^X$

L_{1}^{X}

$L_1^X$

L_{2}^{X}

$L_2^X$

N P^{X}

$NP^X$

Joshua Grochow

Chodziło mi o to, że założenie, że

nie jest wystarczające do wykazania, że te języki są NP-pośrednie, ponieważ nie możemy wykluczyć przypadku, że

ale istnieje algorytm, który rozwiązuje SAT dokładnie na wejściach że

nie jest trywialne, przy czym

byłoby

będzie NPC.

N P \neq P

$NP\neq P$

N P \neq P

$NP\neq P$

L_{1}

$L_1$

L_{1}

$L_1$

P

$P$

L_{2}

$L_2$

Boaz Barak

@Boaz: Ach, oczywiście. Jedną z formalizacji tego jest wyrocznia

taka, że

ale

(które, jak sądzę, podobnie do drugiej wyroczni, o której wspomniałem, nie jest zbyt trudne do zbudowania). (PS - Używając @nazwa, zapewnia, że drugi użytkownik zostanie powiadomiony o twoim komentarzu.)

X

$X$

P^{X} \neq N P^{X}

$P^X \neq NP^X$

L_{1}^{X} \in P

$L_1^X \in P$

Joshua Grochow

@Joshua: Jeśli

niech

będzie maszyną wieloczasową dla

, wówczas

również rozwiąże

ponieważ sprawa bez zapytania do Oracle jest tylko przypadkiem specjalnym. Więc jeśli potrafisz stworzyć

tak, jak to opisujesz, udowodnisz, że

stąd naprawdę nie rozumiem, jak możesz to zrobić.

L_{1}^{X} \in P

$L_1^X\in P$

M

$M$

L_{1}^{X}

$L_1^X$

M

$M$

L_{1}

$L_1$

X

$X$

P_{1} \in P

$P_1\in P$

Arthur MILCHIOR

@Joshua: o swoim pierwszym komentarzu pod Boaz Barak, jeśli

rozwiązać

(na nieskończenie wielu długościach wejściowych), a następnie Chyba chcesz, aby

przynajmniej być wyrocznią dla

. Ale skoro można mieć zapytanie do

w formule #, a następnie w rzeczywistości nawet trzeba

być wyrocznią dla

. Jak możesz pokazać, że taka rekurencyjna definicja jest poprawna? Nie wydaje mi się to wcale jasne. (# Wydaje mi się, że SAT ^ X jest SAT, gdzie X może być również w

M \in P^{X}

$M\in P^X$

S A T^{X}

$SAT^X$

X

$X$

S A T

$SAT$

X

$X$

X

$X$

S A T^{X}

$SAT^X$

zdaniach