Nietrywialne członkostwo w NP

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.

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.

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$

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 krotkax y Q ( x , y ) x y Q I t x Q ( t , y ) Q 1 Q 2 Q 1 I Q 2 I Q 1 Q 2 Q 1 Q 2 Q $\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$

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! :-)

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 )

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 )

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:L 1 , L 2 L 1 ∈ N P L 2 ∉ N P $NP$$L_1, L_2$$L_1\in NP$$L_2\notin NP$$L$

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 ∈ N P N $L\in NP$$L\in NP$$NP$