Naturalne problemy NP-zupełne z „dużymi” świadkami

28

Pytanie dotyczące teorii „ Co to jest NP ograniczony do świadków wielkości liniowej? ” Dotyczy klasy NP ograniczonej do świadków wielkości liniowej , ale $O(n)$

Czy istnieją naturalne problemy NP-zupełne, w których (tak) przypadki wielkości wymagają świadków o rozmiarze większym niż ? $n$ $n$

Oczywiście możemy budować sztuczne problemy, takie jak:

$L = \{ 1^nw \mid w \text{ encodes a satisfiable formula and } |w|=n \}$
$L = \{ \varphi \mid \varphi \text{ is SAT formula with more than } |\varphi|^2 \text{ satisfying assignments}\}$

Po krótkim spojrzeniu na G&J wydaje się, że każdy naturalny problem NPC ma świadków (ściśle) mniejszych niż . $n$

Czy jest na to „powód / wyjaśnienie”?

cc.complexity-theory np proof-complexity Marzio De Biasi
źródło

1

Wiele problemów ma wielkość świadka

, takich jak izomorfizm grafów i ścieżka hamiltonowska. Czy chcesz wykluczyć czynniki polilogowe, czy to liczy się jako odpowiedź?

Θ (n \log n)

$\Theta(n \log n)$

Joshua

12

W rzeczywistości rozmiar świadka dla izomorfizmu grafu i ścieżki hamiltonianu można uznać za podliniowy na wejściu (biorąc pod uwagę, że wejście jest macierzą przylegania

wykresu).

n \times n

$n \times n$

Ryan Williams

1

Och, racja ... d'oh.

Joshua Grochow

1

@MarzioDeBiasi Myślę, że twoja obserwacja małych świadków powinna być wykorzystana do zdefiniowania naturalnego problemu NP-zupełnego.

Mohammad Al-Turkistany

1

@MarzioDeBiasi - Zgadzam się, że wystarczy lista satysfakcjonujących zadań, ale czy możesz udowodnić, że nie ma krótszego świadka problemu? (może zwięzły sposób reprezentowania potrzebnych zadań).

RB

10

Co powiesz na numer kolorowania krawędzi na gęstym wykresie (aka indeks chromatyczny )? Dostajesz macierz przyległości wykresu wierzchołków ( bitowe wejście), ale naturalny świadek opisujący kolorowanie ma rozmiar . Oczywiście mogą istnieć krótsze dowody dla grafów klasy 1 w twierdzeniu Vizinga . $n$ $n^2$ $n^2\log n$

Zobacz także to prawdopodobnie powiązane pytanie

Andreas Björklund
źródło

2

To dobry przykład! Tylko uwaga: problem jest NP-zupełny nawet dla wykresów sześciennych; w takim przypadku mamy świadka wielkości

wystarczą bity (dwa bity na każdą krawędź), która jest mniejsza niż

jeśli użyjemy reprezentacji macierzy przyległości i podejrzewam, że jest mniejsza niż rozmiar instancji, niezależnie od rozsądnego kodowania używanego dla wykresu sześciennego.

2 | E |

$2|E|$

n^{2}

$n^2$

Marzio De Biasi,

8

Natknąłem się na całkiem naturalne problemy kompletne z NP, które najwyraźniej wymagają długich świadków. Problemy sparametryzowane liczbami całkowitymi i są następujące: $C$ $D$

$M$
$n\in\mathbb{N}$ $M$ $Cn+D$ $n$

$M$ $Cn+D$ $Cn+D$ $n$ $n$

$Cn+D$ $q^{O(C)}$ $q$ $q^{O(C)}$ $C\geq 2$ $D\geq 1$

$q^{\Omega(C)}$ $O(q^2)$

David G.
źródło

3

φ

$\varphi$

| φ |^{2}

$|\varphi|^2$

φ

$\varphi$

7

Oto przykład, który wydaje się naturalnym problemem.

$d_1,\ldots,d_n$ $k$ $n$

$k$ $d_1,\ldots,d_n$

$O(n\log n)$ $\Omega(n^2)$

$k$

Andras Farago
źródło

n

$n$

k

$k$

Q

$Q$

Q

$Q$

Zgadzam się, że wydaje się mało prawdopodobne, aby sekwencja stopni + właściwość była zawsze w P, ale może niektóre z nich są kandydatami do statusu NP-pośredniego?

András Salamon,

@ AndrásSalamon Tak, bardzo dobrze mogę sobie wyobrazić, że niektóre z nich mają status NPI.

Andras Farago,

6

Być może jest to głupie „powód / wyjaśnienie”, ale w przypadku wielu problemów NP-Complete rozwiązaniem jest podzbiór danych wejściowych (plecak, pokrywa wierzchołków, klika, dominujący zestaw, niezależny zestaw, maksymalne cięcie, suma podzbiorów, ... ) lub permutacja lub przypisanie do podzbioru danych wejściowych (ścieżka Hamiltona, podróżny sprzedawca, SAT, izomorfizm wykresów, kolorowanie wykresów, ...).

Możemy spróbować przeczytać więcej na ten temat lub wymyślić bardziej wymyślny powód, ale nie jestem pewien, czy dzieje się coś głębszego, czy nie.

usul
źródło

Myślę, że to naprawdę dobry „pierwszy pomysł”. Czasami problemów nie można jednoznacznie sklasyfikować. Na przykład SAT może również stanowić problem z podzbiorem („wybierz podzbiór prawdziwych zmiennych”). A może HAMCYCLE to problem permutacji na wierzchołkach, czy problem podzbioru na krawędziach? (BTW, być może „problemy z przypisaniem” mogą być tak naprawdę „problemami z partycjami”, pomyślmy na przykład o 3-kolorowaniu).

Juho

3

Jeśli chodzi o twoje pierwsze pytanie, Allender stwierdza (w Amplifying Lower Bounds by Meigh of Self-Redukbility ), że nie wiadomo, że żaden naturalny problem NP-zupełny leży poza NTIME (n). Oznacza to, że wszystkie znane naturalne kompletne NP mają świadków wielkości liniowej.

Mohammad Al-Turkistany
źródło

1

Zauważ, że długość najdłuższej ścieżki akceptacji w niedeterministycznej maszynie Turinga odpowiada wielkości świadka.

Mohammad Al-Turkistany

1

Rozważ następujący wariant problemu MAXCLIQUE .

$C$ $2n$ $n$ $2^n$ $n$ $2n$ $C$ $G(C)$ $n$ $C$

$G(C)$ $n^k$ $k$

Uwagi:

$NP$ $N=2n^k$ $G(C)$ $N$ $N$ $C$ $C$ $n$ $N$ $N/2$ $N$ $N$ $N$ $N=2n^k$
$n^k$ $O(n^{k+1})$ $n$ $n^k$ $k$ $C$ $n$ $k$ $C$
Problem można postrzegać jako naturalny, ponieważ jest to wariant MAXCLIQUE .
$NTIME(n)$

Andras Farago
źródło

n

$n$

G^{'}

$G'$

N = 2 n^{k}

$N=2n^k$

C

$C$

(u, v)

$(u,v)$

u \leq N, v \leq N

$u\leq N, \; v\leq N$

(u, v) \in E (G^{'})

$(u,v)\in E(G')$

C

$C$

C

$C$

G (C)

$G(C)$

G^{'}

$G'$

N

$N$

2^{n} - N

$2^n-N$

G (C)

$G(C)$

n^{k}

$n^k$

G^{'}

$G'$ ma półklkę.

Andras Farago,

Naturalne problemy NP-zupełne z „dużymi” świadkami

Odpowiedzi: