Könnte es eine extrem große versteckte Teilmenge von polynomiell lösbaren Problemen innerhalb von NP-Complete-Problemen geben?

Angenommen, P! = NP.

Wir wissen, dass wir jederzeit einfache Instanzen von 3-SAT erstellen können. Wir können auch etwas generieren, von dem wir glauben, dass es harte Instanzen sind (weil unsere Algorithmen sie nicht schnell lösen können). Gibt es irgendetwas, das verhindert, dass die Menge der harten Instanzen beliebig klein ist, solange es für eine bestimmte Instanzgröße (n) nur Poly (n) (oder sogar konstante) Instanzen der Größe Poly (n) oder kleiner gibt?

Für jede harte 3-SAT-Instanz müssten wir die Menge aller 3-SAT-Instanzen hinzufügen, auf die sie reduziert wird, indem der NP-Vollständigkeitsreduktionszyklus durchlaufen wird, aber ich sehe nicht voraus, dass dies die Anzahl der harten Instanzen sehr stark erhöht .

In dieser Welt könnten wir einen Algorithmus konstruieren, der alle NP-vollständigen Probleme polynomiell löst, mit Ausnahme einiger weniger.

Edit: Eine weichere Variante der Frage: Selbst wenn wir P! = NP zeigen würden, wie könnten wir wissen, ob eine gegebene Methode zur Erzeugung von 3-SAT-Problemen der Größe n tatsächlich eine harte mit einer erforderlichen Wahrscheinlichkeit erzeugt? Wenn es keine Möglichkeit gibt, von P! = NP allein zu wissen, was ist erforderlich, um zu zeigen, dass wir ein hartes NP-vollständiges Problem erzeugen können?

1) Je nachdem, was genau gemeint war, kann die Schlussfolgerung in Beobachtung von zu , wobei im Wesentlichen Theorem verwendet wird. Das heißt, wenn es einen Algorithmus gibt, der SAT löst und in der Zeit auf allen Instanzen der Länge läuft, außer möglicherweise solchen Fällen, in denen und beide Polynome sind, dann tatsächlich . Siehe z. B. Meyer und Paterson und Referenzen darin oder Schonings Monographie "Komplexität und Struktur"$\mathsf{NP} \subseteq \mathsf{P/poly}$$\mathsf{P} = \mathsf{NP}$$\leq p(n)$$n$$q(n)$$p$$q$$\mathsf{P} = \mathsf{NP}$. Wenn dies Ihre Vorstellung von "harten Instanzen" erfasst, muss es mehr als viele harte Instanzen für jedes , vorausgesetzt .$poly(n)$$n$$\mathsf{P} \neq \mathsf{NP}$

Zu , solche Algorithmen werden manchmal als "apt" - oder "APT" -Algorithmen für "fast polynomielle Zeit" bezeichnet (nicht zu verwechseln mit der moderneren Komplexitätsklasse , die gleich ).$\mathsf{almostP}$$\mathsf{BPP}$

2) Das Obige kann wie folgt noch weiter verstärkt werden. Angenommen, . Dann sagt das Obige, dass es für jeden Algorithmus, der SAT und jedes Polynom löst , eine Reihe von Instanzen von Superpolynomgröße gibt, bei denen der Algorithmus mehr als Zeit benötigt. Die Menge kann jedoch vom Algorithmus abhängen.$\mathsf{P} \neq \mathsf{NP}$$p$$p(n)$

Das stärkere Ergebnis schaltet die Quantifizierer um und kommt zu dem Schluss: Es gibt eine Superpolynomgrößenmenge H (für "hart"), so dass für jeden Algorithmus A, der SAT löst, und für jedes Polynom p, A mehr als Zeit benötigt endlich viele Elemente von H. Ein solches H wird als Komplexitätskern bezeichnet (die Größenannahme ist nicht Teil der Definition des Komplexitätskerns). Die Definition und Existenz von Komplexitätskernen wurde von Lynch gegeben . Das Ergebnis, das ich gerade zitiert habe, wird von Orponen und Schoning bewiesen .$p(n)$

Niemand hat Impagliazzos berühmtes "Fünf Welten" -Papier erwähnt.

http://www.cs.ucsd.edu/users/russell/average.ps

ein anderer Blickwinkel auf diese Frage (außerhalb des Verweises auf Mahaneys Theorem). Der "Übergangspunkt" in SAT ist eine Untersuchung dieses Phänomens der Verteilung von einfachen und harten Instanzen, insbesondere um einen "kritischen Punkt", an dem die Wahrscheinlichkeit von harten Instanzen maximiert wird. Die Literatur zu diesem Thema ist lang und komplex. Es hat sowohl empirische als auch analytische Ansätze. es ist eng mit der Physik / Thermodynamik verbunden. [3] Leider gibt es derzeit keinen Wikipedia-Eintrag zu diesem sehr wichtigen und grundlegenden Thema der Komplexitätstheorie. Außerdem scheint es nicht viele allgemeine oder "Standard" -Umfragen zu diesem Thema zu geben. Hier ist ein neuer Hinweis, der mit SAT- [1] und TCS-Phasenübergängen im Allgemeinen beginnen soll. [4] Ihre Frage fällt auch in eine Kategorie von "$\stackrel{?}{=}$

Gibt es irgendetwas, das verhindert, dass die Menge der harten Instanzen beliebig klein ist, solange es für eine bestimmte Instanzgröße (n) nur Poly (n) (oder sogar konstante) Instanzen der Größe Poly (n) oder kleiner gibt?

wieder antwortet Mahaneys Theorem (etwas anders formuliert) direkt darauf. Eine andere Sichtweise ist, dass Versuche, die Verteilung von Instanzen auf eine Schlüssel- / charakteristische Weise einzugrenzen, zu NP-vollständigen Funktionen führen. Ein Beispiel für die Komplexität monotoner Schaltkreise sind "Slice-Funktionen". [2]

[1] Vorhersage der Zufriedenheit beim Phasenübergang Lin Xu, Holger H. Hoos, Kevin Leyton-Brown

[2] Paul ES Dunne: Die Komplexität zentraler Schnittfunktionen. Theor. Comput. Sci. 44: 247 & ndash; 257 (1986)

[3] Analytische und algorithmische Lösung zufälliger Erfüllbarkeitsprobleme M. Mezard, G. Parisi, R. Zecchina

[4] Phasenübergänge bei NP-vollständigen Problemen: eine Herausforderung für Wahrscheinlichkeit, Kombinatorik und Informatik von Moore