NP-vollständige Probleme nicht "offensichtlich" in NP

27

Vielen ist der Gedanke gekommen, dass es in allen von mir gelesenen -Vollständigkeitsnachweisen (an die ich mich erinnern kann) immer trivial ist, zu zeigen, dass ein Problem in liegt und dass es sich um -hard ist der ... schwierige Teil. Was für -vollständige Probleme sind das, deren Polynomzeitprüfer höchst untrivial sind? $\textbf{NP}$ $\textbf{NP}$ $\textbf{NP}$ $\textbf{NP}$

complexity-theory np-complete np Gartenkopf
quelle

9

Nicht NP-vollständig, aber die Mitgliedschaft in NP beim Testen, ob eine Zahl eine Primzahl ist, ist nicht trivial (anstatt zu zeigen, dass es sich um eine Zusammensetzung handelt, die trivial ist). Es ist natürlich bekannt, dass das Problem in P liegt, aber dennoch ist dies ein faszinierender Verifizierer.

Shaull

2

Es war definitiv viel schwieriger zu beweisen, dass sich die meisten NP-vollständigen Probleme in NP befinden, als zu beweisen, dass sich PRIME in NP befindet.

gnasher729

1

Siehe auch die allgemeinere Frage cstheory.stackexchange.com/q/21106/109 bei CS.SE.

András Salamon

19

Es gibt mindestens vier solcher vollständigen Probleme, die im Anhang von Garey und Johnsons COMPUTER UND INTEGRIERBARKEIT aufgeführt sind: Ein Leitfaden zur Theorie der NP-Vollständigkeit . $NP$

[AN6] NICHTTEILBARKEIT EINES PRODUKTPOLYNOMS

INSTANZ: Folgen von Paaren von ganzen Zahlen , wobei jedes und eine ganze Zahl . $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$

FRAGE: Ist nicht durch teilbar ? $\displaystyle \prod_{i=1}^m \left( \displaystyle\sum_{j=1}^k a_i[j] \cdot z^{b_i[j]} \right)$ $z^N - 1$

Referenz: [Plaisted, 1977a] , [Plaisted, 1977b] . Transformation von 3SAT. Der Nachweis der Mitgliedschaft in NP ist nicht trivial und erscheint in der zweiten Referenz.

Die anderen drei, die ich im Anhang gefunden habe, sind:

[LO13] MODAL LOGIC S5-ZUFRIEDENHEIT
[LO19] ZWEITE AUFTRAGSINSTANTIATION
[MS3] NICHT LEBENDIGKEIT VON PETRI-NETZEN MIT FREIER WAHL

Kyle Jones
quelle

Vielen Dank! Ich habe dieses Buch und werde es mir unbedingt ansehen.

Gardenhead

Ich bin mir in Bezug auf dieses Problem ein wenig unklar: (1) Bin ich richtig in der Interpretation von z ist eine Variable, die einen beliebigen ganzzahligen Wert annehmen kann (genau wie eine gewöhnliche lineare / quadratische Gleichung). (2) Somit wäre die Nichtteilbarkeit gleichbedeutend mit der Aussage: "für keinen ganzzahligen Wert von z ist Gleichung A durch B teilbar"?

TheoryQuest1

1

Was ich beim Überfliegen der ersten Seiten des 1977a-Papiers erfuhr, ist, dass eine Größe ist, die sich auf die Anzahl der Nullen des Polynoms bezieht, das Teil der Eingabe ist. Für mehr als das musst du dich leider durch die Zeitung schleichen.

z

$z$

Kyle Jones

4

Hier ist ein Problem aus der Datenbanktheorie, genauer aus der Serialisierbarkeitstheorie.

In Serialisierbarkeit durch Sperren (Seite 249) heißt es:

In Bezug auf die Komplexität der Sicherheit haben Papadimitriou et al. [14] haben gezeigt, dass es schwierig ist, zu testen, ob ein Transaktionssystem nicht sicher ist, und es wurde vermutet, dass das Problem . Aus Satz 3 (in diesem Artikel) folgt, dass dies wahr ist. $\textrm{NP}$ $SSR$ $\textrm{NP}$

Das sichere Problem ist in der Veröffentlichung "Some Computational Problems Related to Database Concurrency Control" von Papadimitriou et al. Leider habe ich keinen Zugang dazu. $SSR$

Hengxin
quelle

2

Für mich gehört die ganzzahlige lineare Programmierung (und die zugehörige quantifierfreie Presburger-Arithmetik) zu dieser Klasse.

Ein naiver Ansatz für ein dimensionales ILP-Problem ist die Iteration durch alle Längen- Vektoren von ganzen Zahlen. Dies ist jedoch ein unbegrenzter Prozess. $n$ $n$

Sie müssen eine Zahlentheorie anwenden, um zu beweisen, dass es eine polynomische Obergrenze für die Größe von Lösungen gibt. Wenn also eine Lösung vorhanden ist, gibt es immer eine polynomisch große Lösung, die als Zertifikat fungiert.

Weitere Informationen finden Sie in der Antwort auf eine Frage, die ich vor einiger Zeit gestellt habe.

jmite
quelle

NP-vollständige Probleme nicht "offensichtlich" in NP

Antworten: