Problemy z NP-zupełnością nie „oczywiście” w NP

27

Wielu przyszło na myśl, że we wszystkich dowodach kompletności , które przeczytałem (które pamiętam), zawsze trywialne jest pokazanie, że problem jest w i pokazanie, że jest to -hard jest ... trudną częścią. Jakie problemy zakończone to te, których weryfikatory czasu wielomianowego są wysoce nietrywialne? $\textbf{NP}$ $\textbf{NP}$ $\textbf{NP}$ $\textbf{NP}$

complexity-theory np-complete np ogrodnik
źródło

9

Niezupełne NP, ale wykazanie członkostwa w NP w testowaniu, czy liczba jest liczbą pierwszą, jest dość nietrywialne (zamiast pokazywania, że jest liczbą złożoną, co jest trywialne). Wiadomo, że problem występuje już w P, ale nadal jest to intrygujący weryfikator.

Shaull,

2

Udowodnienie, że „PRIME” jest w NP, było zdecydowanie trudniejsze niż udowodnienie, że większość problemów NP-zupełnych dotyczy NP.

gnasher729

1

Zobacz także bardziej ogólne pytanie cstheory.stackexchange.com/q/21106/109 na stronie CS.SE.

András Salamon

19

Istnieją co najmniej cztery takie pełnoporcjowych problemy wymienione w dodatku do Garey i Johnsona Komputery i krnąbrność: Przewodnik Teorii Problem NP-zupełny . $NP$

[AN6] NIEZALEŻNOŚĆ POLYNOMII PRODUKTU

INSTANCJA: Sekwencje par liczb całkowitych z każdej a jest liczbą całkowitą . $A_i = \langle (a_i[1],b_i[1]), ..., (a_i[k],b_i[k]) \rangle,\ 1 \leqslant i \leqslant m,$ $b_i[j] \geqslant 0,$ $N$

PYTANIE: Czy $\displaystyle \prod_{i=1}^m \left( \displaystyle\sum_{j=1}^k a_i[j] \cdot z^{b_i[j]} \right)$ nie można podzielić przez $z^N - 1$ ?

Odniesienie: [Plaisted, 1977a] , [Plaisted, 1977b] . Transformacja z 3SAT. Dowód członkostwa w NP nie jest trywialny i pojawia się w drugim źródle.

Pozostałe trzy, które znalazłem w dodatku, to:

[LO13] MODALNA LOGIKA S5-SATISFIABILNOŚĆ
[LO19] INSTALACJA DRUGIEGO ZAMÓWIENIA
[MS3] BRAK ŻYWOTNOŚCI BEZPŁATNYCH WYBORÓW SIECI PETRI

Kyle Jones
źródło

Dzięki! Mam tę książkę, więc sprawdzę ją.

ogrodnik

Jestem trochę niejasny w odniesieniu do tego problemu: (1) Czy mam rację w interpretacji z jest zmienną, która może przyjmować dowolną wartość całkowitą (podobnie jak zwykłe równanie liniowe / kwadratowe). (2) Zatem niepodzielność byłaby równoznaczna z stwierdzeniem, że: „dla żadnej liczby całkowitej równania z A jest podzielne przez B”?

TheoryQuest1

1

To, co zebrałem po przejrzeniu kilku pierwszych stron artykułu 1977a, to fakt, że jest liczbą związaną z liczbą zer wielomianu, który jest częścią danych wejściowych. Co więcej, obawiam się, że będziesz musiał przebrnąć przez gazetę.

z

$z$

Kyle Jones

4

Oto problem z teorii bazy danych, a dokładniej z teorii serializacji.

W Serializowalności przez Blokowanie (Strona 237) mówi to

Jeśli chodzi o złożoność bezpieczeństwa, Papadimitriou i in. [14] wykazał, że testuje, czy system transakcyjny nie jest bezpieczny , i przypuszczał, że problemem jest . Z twierdzenia 3 (w tym artykule) wynika, że to prawda. $\textrm{NP}$ $SSR$ $\textrm{NP}$

-safe problemu można znaleźć w artykule „Niektóre problemy związane z obliczeniowa Database Współbieżnym Kontroli” przez Papadimitriou et al. Niestety nie mam do niego dostępu. $SSR$

hengxin
źródło

2

Dla mnie całkowite programowanie liniowe (i związany z nim arytmetyka Presburger Free w kwantyfikatorze) należą do tej klasy.

Naiwnym podejściem do wymiarowego problemu ILP jest iteracja przez wektorów liczb całkowitych o całej długości . Ale to jest nieograniczony proces. $n$ $n$

Musisz użyć teorii liczb, aby udowodnić, że istnieje wielomianowa górna granica wielkości rozwiązań, co oznacza, że jeśli rozwiązanie istnieje, zawsze istnieje rozwiązanie wielomianowe, które działa jak certyfikat.

Więcej informacji można znaleźć w odpowiedzi na pytanie, które zadałem jakiś czas temu.

jmite
źródło

Problemy z NP-zupełnością nie „oczywiście” w NP

Odpowiedzi: