Muss NP-Vollständigkeit / Härte konstruktiv sein?

Gibt es mit folgenden Eigenschaften:$L\in {\bf NP}$

1. Es ist bekannt, dass P = N P impliziert .$L\in {\bf P}$${\bf P}={\bf NP}$

2. Es gibt keine (bekannte) Polynomzeit Turing Reduktion von (oder ein anderen N P -komplette Problem) zu L .$SAT$${\bf NP}$$L$

Mit anderen Worten, wenn ein Polynomialzeitalgorithmus für den Zusammenbruch bedeutet N P in P , dann ist es notwendig , dass diese „allgemeine Härte“ von L für N P muss irgendwie sein c o n s t r u c t i v e in dem Sinne, dass beispielsweise S A T über eine bestimmte Reduktion auf L reduzierbar sein muss ?$L$${\bf NP}$${\bf P}$$L$${\bf NP}$$constructive$$SAT$$L$

Ja, es gibt solche Mengen, nehmen Sie eine beliebige -Zwischenmenge (jede Menge, die nachweislich N P -Zwischenmenge unter der Annahme von P ≠ N P ist ), z. B. konstruieren Sie eine aus SAT unter Verwendung des Ladner-Theorems.$\mathsf{NP}$$\mathsf{NP}$$\mathsf{P}\neq\mathsf{NP}$

Beachten Sie, dass Ihr als N P -Zwischenproblem betrachtet werden muss, da es in N P ist, aber dafür nicht vollständig ist. Beachten Sie auch , dass Sie davon aus, dass P ≠ N P ansonsten gibt es keine solche ist L wie jedes nicht-triviales Problem vollständig wäre für N P wenn N P = P . Darüber hinaus implizieren die von Ihnen angegebenen Bedingungen keine Vollständigkeit, sodass die Frage im ersten Teil nicht mit der Frage nach der Konstruktivität der Vollständigkeit übereinstimmt.$L$$\mathsf{NP}$$\mathsf{NP}$$\mathsf{P}\neq\mathsf{NP}$$L$$\mathsf{NP}$$\mathsf{NP}=\mathsf{P}$

In Bezug auf die Frage im Titel, dh " Muss -Härte konstruktiv sein?".$\mathsf{NP}$

Die Antwort hängt davon ab, was wir unter "konstruktiv" verstehen. Klassischerweise wird ein Entscheidungsproblem als N P -hart iff definiert$A$$\mathsf{NP}$

was bedeutet

Und nach Cooks Theorem ist dies gleichbedeutend mit

was bedeutet

$A$$f$

Selbst wenn wir keine bestimmte Funktion haben, gibt es klassisch eine Funktion, die besagt, dass es unmöglich ist, dass keine Funktion eine Reduktion ist, was der Aussage entspricht, dass eine Funktion eine Reduktion ist. Um über Konstruktivität zu sprechen, müssen wir rücksichtsvoller sein. Zum Beispiel können wir über Aussagen sprechen , die beweisbar klassisch sind aber nicht konstruktiv (zB Intuitionismus , wo verschiedene Zustand des mathematischen Wissens Sinn, Google für „idealen Mathematiker“ oder überprüfen Sie macht dies ).

Intuitiv erscheint es mir plausibel, dass wir eine solche Aussage anhand eines Widerspruchsbeweises und ohne explizite Reduktionsfunktion beweisen können. Dies bedeutet jedoch nicht, dass es keinen konstruktiven Beweis für die Aussage gibt. Um mehr zu sagen, dass es keinen konstruktiven Beweis gibt, müssen wir spezifischer sein: Beweise in welcher Theorie / in welchem ​​System? Was verstehen wir unter einem konstruktiven Beweis?

$k$

"Isomorphic" unterscheidet sich von einer Turing-Reduktion (tatsächlich deutlich schwächer), aber es wurde gezeigt, dass diese Sets direkt NP-hart sind und meines Wissens ist keine Reduktion auf SAT bekannt. Nach der Definition der NP-Vollständigkeit muss es jedoch eine gewisse Reduktion zwischen den beiden geben. Obwohl dies das Kriterium der "nicht bekannten" Reduktion erfüllt, ist es möglicherweise nicht genau das, wonach Sie suchen.

[1] Joseph, D. und Young, P. Einige Anmerkungen zu Zeugenfunktionen für nichtpolynomielle und nicht vollständige Mengen in NP. Theoretische Informatik. Band 39, S. 225-237. 1985. Elsevier.

Das Folgende ist ein Beispiel für die Frage im Titel. Es stammt aus folgendem Papier: Jan Kratochvil, Petr Savicky und Zsolt Tuza. Ein weiteres Auftreten von Variablen führt dazu, dass die Erfüllbarkeit von trivial zu np-vollständig springt. SIAM Journal on Computing, 22 (1): 203–210, 1993.

Sei f (k) die maximale ganze Zahl r, so dass jede k-SAT-Forumula, in der jede Variable höchstens r Mal vorkommt, erfüllbar ist. Es ist nicht bekannt, ob f (k) berechenbar ist, obwohl dafür relativ enge Grenzen bekannt sind (siehe H. Gebauer, R. Moser, D. Scheder und E. Welzl. Das lokale Lemma und die Zufriedenheit von Lovasz. Effiziente Algorithmen, Seiten 30–54, 2009.).

(k, s) -SAT ist das Problem k-SAT, das auf den Forumlas beschränkt ist, in dem jede Variable zu den meisten Zeiten auftritt.

Kratochvil et al. bewiesen, dass (k, f (k) +1) -SAT NP-vollständig ist. Beachten Sie, dass (k, f (k)) - SAT-Probleme (per Definition) immer erfüllt werden können. Die Reduktion selbst ist nicht konstruktiv: Beachten Sie, dass die Reduktion eine Formel ausgibt, in der jede Variable höchstens f (k) + 1-mal vorkommt, obwohl nicht bekannt ist, dass f (k) berechenbar ist. Die nicht konstruktive Hauptidee ist, dass, obwohl der Wert f (k) unbekannt ist, eine (k, f (k) +1) -SAT-Formel existiert, die nicht erfüllt werden kann, und dass sie diese Formel gemäß ihren Bedürfnissen manipulieren .

Agrawal und Biswas präsentierten eine NP-vollständige Sprache, für die keine Karp- oder Cook-Reduktion bekannt ist. Der Vollständigkeitsnachweis folgt, weil seine Zeugenbeziehung universell ist (die Zeugenbeziehung hat die erforderlichen Verknüpfungs- und Äquivalenzoperatoren, die universell sein müssen). Die Sprache ist in Abschnitt 6.3 in der Referenz angegeben.

M.Agrawal, S.Biswas, Universelle Beziehungen in Verfahren IEEE-Konferenz über Struktur in der Komplexitätstheorie (1992), S. 207–220.