Die gemütlichen Stadtteile "P" und "NP-hard"

40

Sei eine algorithmische Aufgabe. (Dies kann ein Entscheidungsproblem, ein Optimierungsproblem oder eine andere Aufgabe sein.) Nennen wir X "auf der Polynomseite", wenn die Annahme, dass X NP-hart ist, impliziert, dass die Polynom-Hieararchie zusammenbricht. Nennen wir X "auf der NP-Seite", wenn die Annahme, dass X einen Polynomalgorithmus zulässt, impliziert, dass die Polynomhierarchie zusammenbricht.XXXXX

Natürlich ist jedes Problem in P auf der Polynomseite und jedes Problem, das NP-hart ist, ist auf der NP-Seite. Auch Factoring (oder irgendetwas im NP-Schnittpunkt coNP) ist beispielsweise auf der Polynomseite. Der Graphisomorphismus liegt auf der Polynomseite. QUANTUM-SAMPLING ist auf der NP-Seite.

1) Ich interessiere mich für mehr Beispiele (so natürlich wie möglich) für algoritische Aufgaben auf der Polynomseite und (besonders) für mehr Beispiele auf der NP-Seite.

2) Naiv betrachtet ist die NP-Seite eine Art "Nachbarschaft" der NP-harten Probleme, und die P-Seite ist eine "Nachbarschaft von P". Ist es eine richtige Einsicht, Probleme auf der NP-Seite als "wesentlich schwieriger" im Vergleich zu Problemen auf der P-Seite zu betrachten? Oder sogar Probleme auf der NP-Seite als "moralisch NP-hart" zu betrachten?

3) (Dies mag offensichtlich sein, aber ich sehe es nicht.) Befindet sich auf beiden Seiten ein oder gibt es theoretische Gründe zu der Annahme, dass ein solches X unwahrscheinlich ist. Update Die Antwort lautet JA; siehe Yuval Filmus 'Antwort unten.XX

(Wenn diese "Seiten" sich auf tatsächliche Komplexitätsklassen beziehen und ich einige relevante Fachausdrücke oder relevante Ergebnisse vermisse, lassen Sie es mich bitte wissen.)

Aktualisieren:Es gibt mittlerweile mehrere sehr gute Antworten auf die Frage. Wie zuerst von Yuval Filmus bemerkt und erneut erwähnt, ist die Frage nicht formal und es ist eine gewisse Einschränkung des Arguments erforderlich, das zeigt, dass X auf der P-Seite / NP-Seite ist. (Andernfalls kann X die Aufgabe sein, einen beidseitigen Beweis für 0 = 1 vorzulegen.) Abgesehen davon kann es vorkommen, dass Probleme X (echt) auf der NP-Seite die Härte irgendwie erfassen Dies kann jedoch auch bei einigen Problemen auf der P-Seite der Fall sein, bei denen die Härte von SAT nachweislich (sogar geringfügig) geschwächt wird. Yuval Filmus gab eine geschwächte Version von SAT, die auf beiden Seiten ist. Andy Drucker gab (in zwei Antworten) fünf interessante Beispiele, einschließlich eines Verweises auf Schönings niedrige und hohe Hierarchien, und Scott Aaronson gab weitere interessante Beispiele, erwähnte die Frage der Invertierung einer Einwegfunktion, die nahe an der NP-Härte und dennoch auf der P-Seite liegt, und erörterte in seiner Antwort auch den interessanten Fall von QUANTUMSAMPLING. Ich habe ein altes Ergebnis dieser Art von Feige und Lund gefunden.

Gil Kalai
quelle
10
1
Ein Beweis in welchem ​​Beweissystem? Außerdem bricht in einem bestimmten Modell der "Welt" (in welchem ​​Beweissystem auch immer man normalerweise arbeitet) entweder PH zusammen oder es nicht, es sei denn, wir arbeiten in der intuitionistischen Logik.
Yuval Filmus
1
Lieber Yuval und Squark, Hmmm, vielleicht ist es besser zu sagen, dass X auf der P-Seite ist, anstatt über "Ursache" oder "Beweis" zu reden, wenn bekannt ist, dass wenn X NP-hart ist, PH zusammenbricht und X zusammenbricht auf der NP-Seite kollabiert der PH, wenn bekannt ist, dass X in P ist. (Frage 1 und 2 bleiben unverändert und Frage 3 fragt, ob es auf beiden Seiten ein X gibt oder aus irgendeinem theoretischen Grund, dass ein solches X nicht möglich ist.)
Gil Kalai
1
(Um die von Ihnen aufgeworfenen Schwierigkeiten zu vermeiden, die für die Frage interessant, aber nicht unbedingt erforderlich sind, werde ich die Frage umformulieren.)
Gil Kalai
1
GK vermutet, dass es hier einige Fragen gibt, die nichts mit dem Kollabieren von PH zu tun haben, sondern sich möglicherweise nur auf unterschiedliche Komplexitätsklassen zwischen P und NP beziehen. Offen gesagt, es klingt nach einer Frage, wie die (nachgewiesenen) Hartmanis- Sterns Zeithierarchie bildet auf P vs NP ab ... dass es ein Kontinuum gibt und Komplexitätsklassen beweisen (falls vorhanden), dass es in diesem Kontinuum sehr signifikante "Diskontinuitäten" gibt ... auch Ladners scheint relevant ...
vzn

Antworten:

27

Die Begriffe "auf der P-Seite" und "auf der NP-Seite" und natürlich der Fragentitel ermutigen uns, uns eine "gemütliche Nachbarschaft" vorzustellen, die P umgibt, und eine andere "gemütliche Nachbarschaft", die die NP-schwierigen Probleme umgibt. Ich möchte jedoch argumentieren, dass diese beiden Stadtteile überhaupt nicht so "gemütlich" sind!

Als eine erste Beobachtung gibt es Probleme "auf der P-Seite", die "moralisch" viel näher an NP-schwer scheinen als an P. Ein Beispiel, das Gil natürlich vorwegnimmt, ist das allgemeine Problem der Invertierung von Einwegfunktionen ( je nachdem, welche Art von Kürzungen zulässig sind (siehe Bogdanov-Trevisan oder Akavia et al.).

Umgekehrt gibt es auch Probleme "auf der NP-Seite", die "willkürlich weit davon entfernt sind", NP-hart zu sein. Ein dummes Beispiel ist eine Zufallssprache L, mit der Wahrscheinlichkeit 1 über L! Denn wenn solch ein L in P ist, dann ist 0 = 1 und Mathe ist inkonsistent, und deshalb kollabiert auch PH. ;-D

(Man beachte, dass eine zufällige Sprache L auch "auf der P-Seite" ist, mit der Wahrscheinlichkeit 1 über L. Für fast alle L gilt die Eigenschaft, dass, wenn sie NP-hart sind, NP⊆BPP und PH zusammenbrechen. Und das gibt einen Beweis, viel einfacher als die Berufung auf Ladners Theorem, dass es Sprachen auf beiden "Seiten" gibt. In der Tat zeigt er, dass von der unzähligen Unendlichkeit der Sprachen "fast alle" - tatsächlich 100% - sind auf beiden Seiten!)

Das klingt nach jugendlichem Spielen, aber ich möchte eine ernsthafte Lektion daraus ziehen. Ich würde argumentieren, dass, obwohl QUANTUM SAMPLING formal "auf der NP-Seite" ist, dieses Problem kaum näher daran liegt, "moralisch NP-hart" zu sein, als es die Zufallssprache L war. Arkhipov und ich (und unabhängig Bremner-Jozsa-Shepherd) haben gezeigt, dass, wenn QUANTUM SAMPLING in P (oder besser gesagt, in SampBPP, der Klasse der polynomiell lösbaren Stichprobenprobleme) ist, P #P = BPP NP und damit das Polynom-Hierarchie bricht zusammen. Wenn Sie jedoch eine BPP-Maschine sind, bringt Sie ein Orakel für BosonSampling, soweit wir wissen, der Lösung von NP-vollständigen Problemen nicht näher als ein zufälliges Orakel. Nur wenn Sie bereits in der Lage sind, NP-vollständige Probleme zu lösen - sagen wir,NP- Maschine - "bemerken" Sie, dass das BosonSampling-Orakel Ihre Fähigkeiten noch weiter steigert, auf #P. Aber die Eigenschaft, NP auf #P zu steigern, scheint anders zu sein als die Eigenschaft, NP-hart zu sein.

Übrigens ist ein wunderbares offenes Problem, das sich aus Gils Frage ergibt, ob BosonSampling auch "auf der P-Seite" ist. Das heißt, können wir zeigen, dass wenn NP zu BosonSampling reduziert wird, PH zusammenbricht? Während mir vielleicht etwas Offensichtliches fehlt, habe ich auf den ersten Blick keine Ahnung, wie ich so etwas beweisen kann, und ich weiß auch nicht, wie ich die stärkere Folgerung beweisen kann, dass wenn NP then BQP dann PH zusammenbricht.

Scott Aaronson
quelle
In Bezug auf den letzten Absatz ist es auch interessant, ob QUANTUM SAMPLING oder BOSONSAMPLING (auch nur annähernd) in einem Comouter mit SAMPBPP-Fähigkeiten erzielt werden können, der zusätzlich die Fähigkeit besitzt, BQP-Probleme zu lösen.
Gil Kalai
1
@ Gil: Ich stimme zu, das ist eine ausgezeichnete Frage. Wie Alex und ich in Abschnitt 4.1 unserer Arbeit darlegen, würde P ^ # P in BPP ^ NP ^ BQP enthalten sein, wenn dies der Fall wäre. Was mir unwahrscheinlich erscheint, obwohl mir eine starke Intuition fehlt!
Scott Aaronson
1
Hier sind ihre Papiere: cs.berkeley.edu/~luca/pubs/redux-sicomp.pdf people.csail.mit.edu/akavia/2006-stocAGGM.pdf (siehe auch erratum unter people.csail.mit.edu/akavia) /AGGM_errata.pdf ) (Es gab auch frühere verwandte Arbeiten von Feigenbaum und Fortnow.) Grundsätzlich zeigen sie, dass, wenn die Invertierung einer Einwegfunktion unter randomisierten, nicht adaptiven Reduktionen NP-hart ist , dann PH zusammenbricht. Der Fall von adaptiven Reduktionen bleibt offen.
Scott Aaronson
1
In Bezug auf QSAMPLING könnte ich leicht glauben, dass BPP ^ NP ^ QSAMPLING strikt größer ist als BPP ^ NP ^ BQP (obwohl ich es natürlich nicht genau weiß). Aus meiner Sicht würde dies jedoch weniger etwas über "inhärente Unterschiede" zwischen QSAMPLING und BQP aussagen, als lediglich über Unterschiede im Mechanismus für den Zugriff auf Orakel! Denken Sie insbesondere daran, dass die BPP ^ NP-Maschine nach unseren Definitionen die Zufallsbits auswählt, die vom Quantenabtast-Orakel verwendet werden. Und selbst ein praktischer Quantencomputer würde diese Fähigkeit zur Zufallsfixierung nicht bieten, obwohl eine klassische Simulation einer QC dies bieten würde.
Scott Aaronson
1
Gil: Nun, das Invertieren von Einwegfunktionen ist nachweislich gleichbedeutend mit dem Lösen von NP-vollständigen Problemen, abgesehen von zwei Änderungen: (1) Sie müssen keine Worst-Case-Instanzen behandeln, sondern nur Durchschnittsfälle (für effizient abtastbare Verteilungen). und (2) das gleiche Abtastverfahren, das die Instanzen erzeugt, erzeugt auch zufriedenstellende Zuweisungen für sie.
Scott Aaronson
19

Zwei Kommentare, von denen keiner eine Antwort darstellt, die jedoch einige nützliche weiterführende Informationen liefern können.

http://www.informatik.hu-berlin.de/forschung/gebiete/algorithmenII/Publikationen/Abstracts/low.ps.abstr_html

t

http://eccc.hpi-web.de/report/1999/045/

Um es klar auszudrücken, es gibt keine wirklichen Beweise dafür, dass dieses Problem nicht NP-schwer ist oder dass es in irgendeiner Weise einfach ist. Aber es scheint ganz anders zu sein als andere schwierige Probleme in NP. Ich denke, dies ist einer der interessantesten Kandidaten für NP-Zwischenprobleme und keiner, der bekannt ist.

Andy Drucker
quelle
18

X

MiMinloglogi(α,β)

f(n)f(1)=1f(n)f(n+1)Xn(ϕ,1|ϕ|f(|ϕ|))|ϕ|nϕxlognxL(Mf(n))Xnf(n+1)=f(n)+1f(n+1)=f(n)f(n)n

X(ϕ,1|ϕ|f(|ϕ|))ϕX=nXn

XMif(n)inMi

gXnkXf(n)f(n)>knn0gn0(ϕ,1|ϕ|f(|ϕ|))fg

Yuval Filmus
quelle
1
Ich könnte etwas vermissen, aber würde hier nicht JEDER Beweis von Ladners Theorem genauso gut funktionieren?
Scott Aaronson
1
Wahrscheinlich, aber ich denke, Gil sucht nach "natürlichen" Beispielen mit "überzeugenden" Beweisen. Wie ich oben ausgeführt habe, ist es besser, 3 nicht in einem strengen logischen Sinn zu nehmen, da es dann dem Zusammenbruch von PH entspricht.
Yuval Filmus
1
Lieber Yuval, Scott, ich frage mich (dies ist Teil 2 meiner Frage), ob Probleme auf der NP-Seite (einschließlich der oben genannten) "moralisch NP-hart" in dem Sinne sind, dass sie die Härte von SAT manifestieren. Dies ist natürlich eine Frage zu unserer gegenwärtigen Fähigkeit, solche Ergebnisse zu beweisen, und keine strenge CC-Frage. Ich interessiere mich hauptsächlich (Teil 1) für mehr Beispiele (je natürlicher desto besser) auf der P-Seite und der NP-Seite. (Wie Yuval erklärte, regelt Landers Theorem Teil 3) meiner Frage. Es ist schön, die Details von Russells Beweis zu sehen.)
Gil Kalai
10

PHPNP

SATNPSATP=NP

http://people.cs.uchicago.edu/~fortnow/papers/2q.pdf

SATψmnmψnmSAT

In Beantwortung einer Frage von Bodlaender, Downey, Fellows und Hermelin wurde von Fortnow und Santhanam gezeigt, dass eine solche Reduzierung der Komprimierung unwahrscheinlich ist, da sie die Polyhierarchie zum Erliegen bringen würde:

http://people.cs.uchicago.edu/~fortnow/papers/compress.pdf

Ihr Ergebnis gilt für zufällige Verkleinerungen, die einseitige Fehler zulassen. Ich habe ein entsprechendes Ergebnis für zweiseitigen Fehler in nachgewiesen

http://eccc.hpi-web.de/report/2012/112/

(Jedes dieser Papiere liefert tatsächlich stärkere und spezifischere Informationen als die oben angegebenen Ergebnisse.)

PHPPADPHAPPADATFNPAPHA

http://people.cs.uchicago.edu/~fortnow/papers/phq.pdf

XP PHPH

Andy Drucker
quelle
Lieber Andy, vielen Dank für diese zusätzliche Antwort!
Gil Kalai
10

Ich bin auf dieses Ergebnis von Feige und Lund gestoßen, was zeigt, dass es schwierig ist, auch nur teilweise Informationen über die Permanenz einer Zufallsmatrix zu erraten, wenn die Polynomhierarchie nicht zusammenbricht.

Uriel Feige und Carsten Lund, Über die Härte der Berechnung der Permanenz zufälliger Matrizen. Computational Complexity 6 (1996/1997) 101-132.

Lassen Sie mich auch zwei weitere relevante Ergebnisse erwähnen, auf die Uri Feige mich aufmerksam gemacht hat:

Die folgenden zwei Arbeiten wenden dies im Kontext der Kernelisierung an (Algorithmen mit fester Parameterverfolgung).

Hans L. Bodländer, Rodney G. Downey, Michael R. Fellows, Danny Hermelin: Über Probleme ohne Polynomkerne. J. Comput. Syst. Sci. 75 (8): 423-434 (2009)

Lance Fortnow, Rahul Santhanam: Unmöglichkeit der Instanzkomprimierung und prägnanter PCPs für NP. J. Comput. Syst. Sci. 77 (1): 91-106 (2011)

Gil Kalai
quelle
1
Das Ergebnis über durchschnittlichen Fall Härte der permanenten wurde von Cai, Pavan und Sivakumar in verbesserten pages.cs.wisc.edu/~jyc/papers/permanent.pdf
arnab