Nietrywialne członkostwo w NP

27

Czy jest przykładem języka, który jest w $NP$ , ale gdzie nie możemy udowodnić ten fakt bezpośrednio poprzez pokazanie, że istnieje wielomian świadka do członkostwa w tym języku?

Zamiast tego fakt, że język znajduje się w $NP$ , można udowodnić, redukując go do innego języka w $NP$ , gdzie powiązanie między nimi nie jest banalne i wymaga starannej analizy.

Mówiąc bardziej ogólnie, istnieją pewne interesujące przykłady problemów w $NP$ tak, że jest trudno zauważyć, że są one w $NP$ ?

Semi-odpowiedź byłaby problem decydując zwycięzcę w grach parzystości: aby pokazać, że jest w $NP$ (nawet $NP\cap coNP$ ), potrzebujemy pozycyjny gry nieskończone twierdzenie, który jest głęboki i nietrywialne. Jednak ta odpowiedź nie jest idealna, ponieważ nadal sprowadza się do istnienia wielomianu świadka dokładnym tego problemu (Strategię pozycyjny), a nie zmniejsza się do innego innego $NP$ -problem.

Innym byłby algorytm pierwotności AKS: decydowanie, czy liczba jest liczbą pierwszą, jest wielomianowe, podczas gdy z góry nie ma małego świadka tego faktu. Powiedzmy, że wykluczamy „zaskakujące algorytmy wielomianowe”, ponieważ wiele z nich pasowałoby do powyższego opisu. Jestem bardziej zainteresowany zaskakując $NP$ algorytmy, które nie są deterministyczne.

reductions np

— Denis
źródło

12

Wiedzieliśmy, że liczby pierwsze były w NP przed AKS, ponieważ

n > 2

$n > 2$ jest liczbą pierwszą iff istnieje

1 < r < n

$1<r<n$ takie, że i dla wszystkich głównych dzielników q od

,

.

r^{n - 1} = 1 \mod n

$r^{n−1} = 1 \mod n$

n - 1

$n−1$

r^{\frac{n - 1}{q}} \neq 1 \mod n

$r^\frac{n-1}{q} \neq 1 \mod n$

— Artem Kaznatcheev

ciekawe, nie myślałem o świadectwach pierwszeństwa.

— Denis

6

Dobra pula przykładów nietrywialnego członkostwa w NP może wynikać z problemów, dla których od pewnego czasu jest otwarta, czy można je było rozstrzygać. Dwa problemy z góry mojego kapelusza: rozpoznawanie wykresów i rozpoznawanie węzłów (i bardziej ogólny rodzaj węzłów). W obu przypadkach istnieje świadek wielomianowy (mianowicie normalne krzywe / powierzchnie) - po prostu trudno było je znaleźć. Wiązanie występuje również w NP i nie jest również trywialne: istnieje certyfikat, ale potrzeba uogólnionej hipotezy Riemanna, aby wielomian był związany z jego rozmiarem.

— Arnaud

„Problem orbity” również nie był znany przez długi czas. W końcu udowodniono, że jest w P. Prof. Lipton ma doskonały artykuł na swoim blogu o historii tego problemu: rjlipton.wordpress.com/2009/09/02/the-orbit-problem

— Jagadish

3

Jeszcze jeden przykład: biorąc pod uwagę wykres, zdecyduj, czy jest on idealny. Problem można rozwiązać w czasie wielomianowym, ale zajęło trochę czasu, aby udowodnić, że jest w NP.

— Jagadish

20

Programowanie liczb całkowitych .

Wykazanie, że jeśli istnieje rozwiązanie liczb całkowitych, wówczas istnieje rozwiązanie liczb całkowitych o wielomianowym rozmiarze. Widzieć

Christos Papadimitriou, „ On the Complexity of Integer Programming ”, JACM, 1981.

— Kaveh
źródło

4

Patrz Christos Papadimitriou, O złożoności programowania liczb całkowitych , JACM 28 765–768. dx.doi.org/10.1145/322276.322287 (warto przeczytać i mieć tylko cztery strony).

— András Salamon

1

Jeśli nie masz dostępu do ACM DL, możesz uzyskać papier Papadimitriou tutaj .

— Kaveh

17

Podczas gdy problem „czy liczba przecięcia wykresu wynosi co najwyżej ?” jest trywialnie w NP, członkostwo w NP powiązanych problemów dla prostoliniowego numeru przecięcia i numeru przecięcia pary jest wysoce nieoczywiste; por. Bienstock, Niektóre prawdopodobnie trudne problemy z przekraczaniem numeru, Discrete Comput. Geometry 6 (1991) 443-459 oraz Schaefer i in., Recognizing graf string w NP, J. Comput. System Sci. 67 (2003) 365–380. $k$

— użytkownik13136
źródło

13

Moim ulubionym przykładem jest klasyczny wynik Ashoka Chandry i Philipa Merlina z 1977 r . Wykazali, że problem ograniczania zapytań był rozstrzygalny w przypadku zapytań łącznych. Okazało się, że problem ograniczania zapytań łącznych jest równoważny z podejmowaniem decyzji, czy istnieje homomorfizm między dwoma zapytaniami wejściowymi. Przeformułowuje to problem semantyki, obejmujący kwantyfikację w zbiorze nieskończonym, na problem składniowy, wymagający jedynie sprawdzenia skończonej liczby możliwych homomorfizmów. Certyfikat homomorfizmu ma tylko rozmiar liniowy, więc problem dotyczy NP.

Twierdzenie to stanowi jedną z podstaw teorii optymalizacji zapytań do bazy danych. Chodzi o przekształcenie zapytania w inne, szybsze. Jednak chce się mieć pewność, że proces optymalizacji nie utworzy nowego zapytania, które nie da odpowiedzi w niektórych bazach danych, w których oryginalne zapytanie dało wyniki.

Formalnie zapytanie do bazy danych jest wyrażeniem postaci , gdzie to lista wolnych zmiennych, jest listą powiązanych zmiennych, a to formuła pierwszego rzędu ze zmiennymi i języka z symbolami relacji. Zapytanie może zawierać kwantyfikatory egzystencjalne i uniwersalne, formuła może zawierać koniunkcję i rozłączenie atomów relacyjnych, a także może pojawić się negacja. Zapytanie jest stosowane do instancji bazy danych , która jest zbiorem relacji. Wynikiem jest zestaw krotek; kiedy krotka $\mathbf{x}.Q(\mathbf{x},\mathbf{y})$ $\mathbf{x}$ $\mathbf{y}$ $Q(\mathbf{x},\mathbf{y})$ $\mathbf{x}$ $\mathbf{y}$ $Q$ $I$ $\mathbf{t}$ w wyniku zastępuje a następnie można spełnić formułę . Można następnie porównać dwa zapytania: zawarty jest w jeśli kiedykolwiek zastosować do dowolnej instancji bazy danych wytwarza pewne rezultaty, a następnie zastosowane do tej samej instancji produkuje również pewne rezultaty. (Jest w porządku, jeśli nie generuje wyników, ale tak, ale dla powstrzymania implikacja musi być zachowana dla każdej możliwej instancji). Problem powstrzymywania zapytań pyta: biorąc pod uwagę dwa zapytania do bazy danych $\mathbf{x}$ $Q(\mathbf{t},\mathbf{y})$ $Q_1$ $Q_2$ $Q_1$ $I$ $Q_2$ $I$ $Q_1$ $Q_2$ $Q_1$ i , czy jest zawarte w ? $Q_2$ $Q_1$ $Q_2$

Przed Chandra-Merlin nie było wcale jasne, że problem jest rozstrzygalny. Używając samej definicji, należy obliczyć nieskończony zestaw wszystkich możliwych baz danych. Jeśli zapytania są nieograniczone, problem jest w rzeczywistości nierozstrzygalny: niech będzie formułą, która jest zawsze prawdziwa, wtedy jest zawarte w jeśli jest poprawne. (To Entscheidungsproblem Hilberta , pokazany jako niezdecydowany przez Churcha i Turinga w 1936 r.) $Q_1$ $Q_1$ $Q_2$ $Q_2$

Aby uniknąć nierozstrzygalności, zapytanie łączone ma raczej ograniczoną formę: zawiera tylko kwantyfikatory egzystencjalne, a negacja i rozłączenie są niedozwolone. Zatem jest pozytywną formułą egzystencjalną z jedynie połączeniem atomów relacyjnych. Jest to niewielki fragment logiki, ale wystarcza do wyrażenia dużej części przydatnych zapytań do bazy danych. Klasyczna instrukcja w SQL wyraża zapytania łączące; większość zapytań w wyszukiwarkach to zapytania łączone. $Q$ $Q$ SELECT ... FROM

Homomorfizmy między zapytaniami można zdefiniować w prosty sposób (podobnie jak homomorfizm wykresów, z odrobiną dodatkowej księgowości). Twierdzenie Chandra-Merlina mówi: biorąc pod uwagę dwa zapytania i , jest zawarte w iff, istnieje homomorfizm zapytania od do . Ustanawia to członkostwo w NP i łatwo jest pokazać, że jest to również trudne dla NP. $Q_1$ $Q_2$ $Q_1$ $Q_2$ $Q_2$ $Q_1$

Ashok K. Chandra i Philip M. Merlin, Optymalne wdrażanie spójnych zapytań w relacyjnych bazach danych , STOC '77 77–90. doi: 10.1145 / 800105.803397

Rozstrzygalność ograniczania zapytań została później rozszerzona na związki zapytań łączonych (zapytania egzystencjalne dodatnie, w których dozwolone jest rozłączanie), chociaż zezwolenie na rozłączanie podnosi złożoność do . Ustalono również wyniki rozstrzygalności i nierozstrzygalności dla bardziej ogólnej formy ograniczania zapytań , polegającej na przerywaniu wycen, które występują podczas zliczania liczby odpowiedzi, łączenia adnotacji lub pochodzenia wyników zapytań w probabilistycznych bazach danych. $\Pi^P_2$

— András Salamon
źródło

4

Znalazłem dobrego kandydata podczas czytania artykułów na temat kwadratowych równań diofantycznych:

JC Lagarias, Zwięzłe certyfikaty rozwiązań binarnych kwadratowych równań diofantycznych (2006)

Ze streszczenia: ... Niech oznacza długość binarnego kodowania binarnego kwadratowego równania diofantycznego podanego przez . Załóżmy, że jest takim równaniem mającym nieujemne rozwiązanie liczb całkowitych. Ten dokument pokazuje, że istnieje dowód (tj. „Certyfikat”), że ma takie rozwiązanie, które można sprawdzić w bicie operacje. Następstwem tego wyniku jest to, że zestaw należy do klasy złożoności NP ... $L(F)$ $F$ $a x_1^2 +b x_1 x_2+ c x_2^2 +d x_1+e x_2 + f = 0$ $F$ $F$ $O(L(F)^5 \log L(F) \log \log L(F))$ $\Sigma = \{F : F \text{ has a nonnegative integer solution}\}$

... ale - szczerze mówiąc - jedynym dowodem na to, że nie jest to łatwe, jest liczba stron papieru ... 62! :-)

— Marzio De Biasi
źródło

4

Gdy rozpoznawanie wykresu tolerancji było otwarte, następujący artykuł wykazał, że jest w NP:

http://www.sciencedirect.com/science/article/pii/S0166218X04000940

(Później wykazano, że rozpoznawanie wykresu tolerancji jest NP kompletne: http://arxiv.org/abs/1001.3251 )

— JimN
źródło

3

Decydowanie o osiągalności różnych rodzajów systemów o stanie nieskończoności jest czasem rozstrzygalne, a często nie. W niektórych interesujących przypadkach specjalnych zawsze istnieje wystarczająco mały i sprawnie sprawdzalny certyfikat, co powoduje takie problemy w NP. Oto zgrabna obróbka automatów parametrycznych z jednym licznikiem:

Christoph Haase, Stephan Kreutzer, Joël Ouaknine, James Worrell, Osiągalność w zwięzłych i parametrycznych automatach z jednym licznikiem , CONCUR 2009, LNCS 5710 369–383. doi: 10.1007 / 978-3-642-04081-8_25 ( wersja rozszerzona )

— András Salamon
źródło

3

Oto przykład (choć wprawdzie sztuczny), kiedy bardzo trudno jest zdecydować, czy problem dotyczy czy nie. Niech będą dwoma językami, z , a . Teraz zdefiniuj język w następujący sposób: $NP$ $L_1, L_2$ $L_1\in NP$ $L_2\notin NP$ $L$

L = L_{1} if the twin prime conjecture is true, and L = L_{2} otherwise

$L=L_1 \; \mbox{if the twin prime conjecture is true, and } \; L=L_2 \; \mbox{otherwise}$

Wtedy dokładnie, jeśli hipoteza podwójnej liczby pierwszej jest prawdziwa. Ponieważ przypuszczenie jest prawdziwe, czy nie, jest rzeczywiście dobrze określone, czy czy nie. Jednak decydowanie, co się dzieje, to znaczy decydowanie o członkostwie w , sprowadza się do rozwiązania słynnej hipotezy o podwójnej liczbie pierwszych, więc z pewnością nie jest to łatwe ... $L\in NP$ $L\in NP$ $NP$

— Andras Farago
źródło

5

Jest to nie tylko sztuczne, ale sztuczne w pewien zabawny sposób: nie podałeś TM, która decyduje o L, ale bardziej przypomina „Jeśli [hipoteza podwójnej liczby pierwszej], to TM to A, a w przeciwnym razie to B.” Możesz uzyskać podobny sztuczny przykład, ale bez tej „zabawy” w następujący sposób:naruszając hipotezę podwójnych liczb pierwszych . Możemy zapisać jedną niedeterministyczną bazę danych TM, która decyduje o tym języku (zamiast instrukcji warunkowej opisującej dwie możliwe bazy TM). Wynikowy język to lub skończony.

L = {x : x \in L_{2} \land \neg \exists m \leq | x |

$L = \{x : x \in L_2 \wedge \neg\exists m \leq |x|$

}

$\}$

L_{2}

$L_2$

— Joshua Grochow