Nichttriviale Mitgliedschaft in NP

Gibt es ein Beispiel für eine Sprache, die in , aber wo wir diese Tatsache nicht direkt beweisen können, indem wir zeigen, dass es ein polynomisches Zeugnis für die Zugehörigkeit zu dieser Sprache gibt?$NP$

Stattdessen würde die Tatsache, dass die Sprache in , durch Reduzieren auf eine andere Sprache in bewiesen , wobei die Verbindung zwischen den beiden nicht trivial ist und eine sorgfältige Analyse erfordert.$NP$$NP$

Gibt es allgemein einige interessante Beispiele für Probleme in so dass es schwer zu erkennen ist, dass sie in ?$NP$$NP$

Eine Halbantwort wäre das Problem, den Sieger in Paritätsspielen zu bestimmen: zu zeigen, dass es sich um (auch ), benötigen wir den Satz der Positionsbestimmung, der tief und nicht trivial ist. Diese Antwort ist jedoch nicht ideal, da sie immer noch auf die Existenz eines polynomischen Zeugen für dieses genaue Problem (die Positionsstrategie) hinausläuft und sich nicht auf ein anderes Problem reduziert .$NP$$NP\cap coNP$$NP$

Ein anderer wäre der AKS-Primalitätsalgorithmus: Die Entscheidung, ob eine Zahl eine Primzahl ist, ist polynomisch, während es a priori keinen kleinen Beweis für diese Tatsache gibt. Nehmen wir an, wir schließen die "überraschenden Polynomalgorithmen" aus, da viele von ihnen der obigen Beschreibung entsprechen würden. Ich interessiere mich mehr für überraschende Algorithmen, die nicht deterministisch sind.$NP$

Integer-Programmierung .

Zeigen, dass es eine ganzzahlige Lösung gibt, wenn es eine ganzzahlige Lösung mit polynomischer Größe gibt. Sehen

• Christos Papadimitriou, " Über die Komplexität der Integer-Programmierung ", JACM, 1981.

Während das Problem "ist die Kreuzungszahl eines Graphen höchstens ?" ist in NP trivialerweise die NP-Zugehörigkeit der damit verbundenen Probleme für die geradlinige Kreuzungszahl und die Paarkreuzungszahl hochgradig nicht offensichtlich; vgl. Bienstock, Einige wahrscheinlich schwierige Zahlenprobleme, Discrete Comput. Geometry 6 (1991) 443-459 und Schaefer et al., Recognising string graphs in NP, J. Comput. System Sci. 67 (2003) 365-380.$k$

Mein Lieblingsbeispiel ist ein klassisches 1977er Ergebnis von Ashok Chandra und Philip Merlin. Sie zeigten, dass das Problem der Eingrenzung von Abfragen für konjunktive Abfragen entschieden werden kann. Das Conjunctive-Query-Containment-Problem stellt sich als äquivalent zur Entscheidung heraus, ob es einen Homomorphismus zwischen den beiden Eingabeabfragen gibt. Dies formuliert ein Semantikproblem, das die Quantifizierung über eine unendliche Menge beinhaltet, in ein syntaktisches Problem um, bei dem nur eine endliche Anzahl möglicher Homomorphismen überprüft werden muss. Das Homomorphismuszertifikat hat nur eine lineare Größe und das Problem liegt in NP.

Dieser Satz liefert eine der Grundlagen der Theorie der Datenbankabfrageoptimierung. Die Idee ist, eine Abfrage in eine andere, schnellere umzuwandeln. Man möchte jedoch die Gewissheit haben, dass durch den Optimierungsprozess keine neue Abfrage erstellt wird, die in einigen Datenbanken, in denen die ursprüngliche Abfrage Ergebnisse erbracht hat, keine Antworten liefert.

Formal ist eine Datenbankabfrage ein Ausdruck der Form , wobei eine Liste freier Variablen ist, ist eine Liste gebundener Variablen, und ist eine Formel erster Ordnung mit den Variablen und einer Sprache mit Beziehungssymbolen. Die Abfrage kann existenzielle und universelle Quantifizierer enthalten, die Formel kann Konjunktion und Disjunktion von relationalen Atomen enthalten, und es kann auch Negation auftreten. Eine Abfrage wird auf eine Datenbankinstanz angewendet , bei der es sich um eine Reihe von Beziehungen handelt. Das Ergebnis ist eine Menge von Tupeln; wenn Tupel$\mathbf{x}.Q(\mathbf{x},\mathbf{y})$$\mathbf{x}$$\mathbf{y}$$Q(\mathbf{x},\mathbf{y})$$\mathbf{x}$$\mathbf{y}$$Q$$I$$\mathbf{t}$ im Ergebnis wird durch dann kann die Formel erfüllt werden. Man kann dann zwei Abfragen vergleichen: ist in Wenn auf eine beliebige Datenbankinstanz angewendet wird und einige Ergebnisse , wird auf dieselbe Instanz angewendet und erzeuge auch einige Ergebnisse. (Es ist in Ordnung, wenn keine Ergebnisse liefert, jedoch, aber für die Eindämmung muss die Implikation für jede mögliche Instanz gelten.) Das Problem mit der Eindämmung von Abfragen : Bei zwei Datenbankabfragen$\mathbf{x}$$Q(\mathbf{t},\mathbf{y})$$Q_1$$Q_2$$Q_1$$I$$Q_2$$I$$Q_1$$Q_2$$Q_1$und , ist in ?$Q_2$$Q_1$$Q_2$

Es war vor Chandra-Merlin überhaupt nicht klar, dass das Problem entschieden werden konnte. Mit nur der Definition muss man über die unendliche Menge aller möglichen Datenbanken quantifizieren. Wenn die Abfragen uneingeschränkt sind, ist das Problem tatsächlich nicht zu entscheiden: Sei eine Formel, die immer wahr ist, dann ist in wenn gültig ist. (Dies ist Hilberts Entscheidungsproblem , das 1936 von Church and Turing als unentscheidbar erwiesen wurde.)$Q_1$$Q_1$$Q_2$$Q_2$

Um Unentscheidbarkeit zu vermeiden, hat eine Konjunktivabfrage eine eher eingeschränkte Form: enthält nur existenzielle Quantifizierer, und Negation und Disjunktion sind nicht zulässig. So ist eine positive Existenz Formel mit nur Verbindung relationaler Atom. Dies ist ein winziges Fragment der Logik, aber es reicht aus, um einen großen Anteil nützlicher Datenbankabfragen auszudrücken. Die klassische Anweisung in SQL drückt konjunktive Abfragen aus. Die meisten Suchmaschinenabfragen sind konjunktive Abfragen.$Q$$Q$SELECT ... FROM

Man kann Homomorphismen zwischen Abfragen auf einfache Weise definieren (ähnlich dem Diagrammhomomorphismus mit ein wenig zusätzlicher Buchhaltung). Das Chandra-Merlin-Theorem besagt: Bei zwei konjunktiven Abfragen und ist in wenn es einen Abfrage-Homomorphismus von bis . Dies begründet die Mitgliedschaft in NP, und es ist unkompliziert zu zeigen, dass dies auch NP-schwer ist.$Q_1$$Q_2$$Q_1$$Q_2$$Q_2$$Q_1$

• Ashok K. Chandra und Philip M. Merlin, Optimale Implementierung konjunktiver Abfragen in relationalen Datenbanken , STOC '77 77–90. doi: 10.1145 / 800105.803397

Die Entscheidbarkeit der Abfrageeinschließung wurde später auf Vereinigungen von konjunktiven Abfragen (existentielle positive Abfragen, bei denen die Disjunktion zulässig ist) erweitert, obwohl das Zulassen der Disjunktion die Komplexität auf -complete erhöht. Entscheidbarkeits- und Unentscheidbarkeitsergebnisse wurden auch für eine allgemeinere Form der Abfragebegrenzung festgelegt , bei der es sich um Zwischenbewertungen handelt, die beim Zählen der Anzahl der Antworten, beim Kombinieren von Anmerkungen in der Provenienz oder beim Kombinieren der Ergebnisse von Abfragen in probabilistischen Datenbanken auftreten.$\Pi^P_2$

Ich habe einen guten Kandidaten gefunden, als ich einige Artikel über quadratische Diophantingleichungen gelesen habe:

JC Lagarias, Kurzzertifikate für Lösungen zu binären quadratischen Diophantin-Gleichungen (2006)

Aus der Zusammenfassung: ... Es sei die Länge der binären Codierung der binären quadratischen Diophantin-Gleichung die durch . Angenommen, ist eine solche Gleichung mit einer nichtnegativen ganzzahligen Lösung. Dieses Dokument zeigt, dass es einen Beweis (dh ein "Zertifikat") dafür gibt, dass eine solche Lösung hat, die im Bit überprüft werden kann Operationen. Eine Folge dieses Ergebnisses ist, dass die Menge in der Komplexitätsklasse NP liegt ...$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}\}$

... aber - um ehrlich zu sein - der einzige Beweis, den ich habe, dass es nicht trivial ist, ist die Anzahl der Seiten des Papiers ... 62! :-)

Als die Erkennung von Toleranzgraphen geöffnet war, zeigte das folgende Papier, dass es sich um NP handelt:

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

(Später wurde gezeigt, dass die Toleranzgraphenerkennung NP-vollständig ist: http://arxiv.org/abs/1001.3251 )

Die Entscheidung über die Erreichbarkeit verschiedener Arten von Infinite-State-Systemen ist manchmal entscheidend, oft nicht. Für einige interessante Sonderfälle gibt es immer ein ausreichend kleines und effizient überprüfbares Zertifikat, das solche Probleme in NP einbringt. Hier ist eine übersichtliche Behandlung für parametrische Automaten mit einem Zähler:

• Christoph Haase, Stephan Kreutzer, Joël Ouaknine, James Worrell, Erreichbarkeit in prägnanten und parametrischen Ein-Zähler-Automaten , CONCUR 2009, LNCS 5710 369–383. doi: 10.1007 / 978-3-642-04081-8_25 ( erweiterte Version )

Hier ist ein Beispiel (obwohl zugegebenermaßen künstlich), bei dem es sehr schwer ist zu entscheiden, ob ein Problem in oder nicht. Sei zwei Sprachen mit und . Definieren Sie nun die Sprache wie folgt:$NP$$L_1, L_2$$L_1\in NP$$L_2\notin NP$$L$

Dann genau dann, wenn die Twin-Prime-Vermutung wahr ist. Da die Vermutung entweder wahr ist oder nicht, ist es tatsächlich gut definiert, ob oder nicht. Zu entscheiden, was der Fall ist, das heißt, die Mitgliedschaft in , bedeutet jedoch, die berühmte Twin-Prime-Vermutung zu lösen. Es ist also sicher nicht trivial ...$L\in NP$$L\in NP$$NP$