Frage:
Kann ein Parallelcomputer einen Quantencomputer simulieren? Ist BQP in NP?
Ron Maimon
2012-08-20 01:57:44 UTC
view on stackexchange narkive permalink

Wenn Sie einen klassischen Computer mit unendlichem Speicher und unendlicher Prozessornummer haben und beliebig viele Threads abspalten können, um ein Problem zu lösen, haben Sie eine sogenannte "nichtdeterministische" Maschine. Dieser Name ist irreführend, da er nicht probabilistisch oder quantenmäßig, sondern parallel ist, aber in Kreisen der Komplexitätstheorie leider Standard ist. Ich ziehe es vor, es "parallel" zu nennen, was eher Standard ist.

Kann ein Parallelcomputer einen Quantencomputer simulieren? Ich dachte, die Antwort lautet "Ja", da Sie so viele Prozesse ausführen können, wie Sie zur Simulation der verschiedenen Zweige benötigen. Dies ist jedoch kein Beweis, da Sie die Zweige möglicherweise erneut zusammenfassen, um ein PSPACE-Problem zu lösen, das nicht parallel lösbar ist.

Gibt es ein Problem ausschließlich in PSPACE, nicht in NP, das in BQP ist? Kann ein Quantencomputer ein Problem lösen, das von einer Parallelmaschine nicht gelöst werden kann?

Jargongloss

  1. BQP: (Begrenzter Fehler Quantenpolynomzeit) Die Klasse der lösbaren Probleme durch einen Quantencomputer in mehreren Schritten Polynom in der Eingangslänge.
  2. NP: (Nichtdeterministische Polynomzeit) die Klasse von Problemen, die durch eine möglicherweise unendlich parallele ("nichtdeterministische") Maschine in Polynomzeit
  3. P: (Polynomzeit) die Klasse von Problemen, die von einem einzelnen Prozessorcomputer in Polynomzeit gelöst werden können
  4. PSPACE: Die Klasse von Problemen, die mit einer polynomiellen Speichermenge gelöst werden können, aber unbegrenzte Laufzeit.
    5. ol>
Ich denke, eine interessantere Frage ist, ob ein Quantencomputer, den wir bauen könnten, "klassischen Computer mit unendlichem Speicher und unendlicher Prozessornummer" simulieren könnte.
@Yrogirg: Das wird allgemein als falsch vermutet - das ist die Aussage, die der BQP NP enthält, und sie wird nicht ernst genommen. Es würde einen Quantenalgorithmus für ein NP-vollständiges Problem erfordern. Dies zu beweisen ist natürlich hoffnungslos, da es P! = NP automatisch beweisen würde.
Ich dachte, "unendlicher Speicher unendliche Prozessornummer klassischer Computer" sollte in der Lage sein, bestimmte Super-Turing-Berechnungen durchzuführen, wie das Testen jeder ganzen Zahl. Ich habe mich gefragt, ob ein Quantencomputer das kann.
@Yrogirg: Oh, ich verstehe --- das stimmt nicht, weil Sie den Prozessorstatus initialisieren müssen, um jedem der Prozessoren mitzuteilen, was zu tun ist. Sie können beliebig viele Prozessoren auf einem einzigen simulieren, was Speicher- und Verlangsamungskosten verursacht. Wenn diese Prozessoren keinen gemeinsamen Speicher haben und alle Prozesse wie unter Unix durch einen Fork-Befehl verzweigt sind, erhalten Sie eine "nicht deterministische" Maschine, und es ist ein offenes Problem, wenn sie sogar schneller als eine normale Einzelprozessor-Maschine ist asymptotisch (obwohl es offensichtlich wahr ist). Dies ist P! = NP.
Vorschlag zur Frage (v1): Zum Nutzen neuer Leser ist es eine gute Idee, Abkürzungen zu formulieren.
@Qmechanic: Ich habe es getan, aber ich bin nicht sicher, ob es notwendig ist, da ich darauf geachtet habe, alles zweimal anzugeben, zuerst ohne Jargon, dann mit.
@Yrogirg: Ron Maimons Aussage, dass ein Quantencomputer wahrscheinlich keinen unendlichen Speicher simulieren kann, ein Computer mit unendlichem Prozessor ist nicht nur richtig, er ist eine enorme Untertreibung. Obwohl Ron in diesem Punkt nicht mit mir übereinstimmt, wird im Bereich der Quanteninformationstheorie allgemein akzeptiert, dass [Quantenzustände * nicht einmal exponentiell * mehr Informationen enthalten als klassische Zustände] (http://physics.stackexchange.com/ Fragen / 10364 / do-Quantenzustände-enthalten-exponentiell-mehr-Informationen-als-klassische-Zustände / 15512 # 15512).
@NieldeBeaudrap: Ich weiß nicht, was Sie unter "nicht einverstanden" verstehen. Ich bin nur anderer Meinung, dass Sie zur klassischen Simulation eines Quantencomputers Polynomressourcen benötigen, und dies wird auch gut akzeptiert. Ich denke, das ist nur Terminologie.
@RonMaimon: genau das meine ich, worüber wir uns nicht einig sind. * Nach den Techniken, die wir derzeit besitzen *, reichen polynomielle Ressourcen nicht aus. Das heißt nicht, dass * es nicht nur mit Polynomressourcen möglich ist *, und dass diese Ressourcen wie bei Münzwürfen zufällig vorbereitet werden können.
@NieldeBeaudrap: Sie denken also, dass Sie Zahlen in der Polynomzeit berücksichtigen können, indem Sie Münzen werfen? Aus diesem Grund kann man sicher sein, dass Sie die Anzahl der benötigten Münzwürfe anhand eines heuristischen Arguments für die Härte des Factorings abschätzen können. Meiner Meinung nach ist es (im wissenschaftlichen Sinne) sicher, dass man mit Polynomressourcen nicht naiv faktorisieren kann (was bedeutet, ohne mehr über Factoring zu wissen als das, was man in Shors Algorithmus lernt), und ich glaube auch, dass Factoring wirklich nicht polynomisch ist das gleiche heuristische Argument (das erklärt, warum P! = NP), so dass es keinen polynomiellen Quantenzustand gibt.
Für andere: Niel ist irreführend und falsch darüber, dass der Quantenzustand keine exponentiellen Informationen "hat". Was er bemerkt, ist, dass Sie nicht mehr als die klassische Informationsmenge in einem Quantenzustand codieren und extrahieren können, aber das sagt nichts aus - die Darstellung eines Quantenzustands zu Zwischenzeiten hängt nicht von der Informationsmenge ab, die Sie können raus durch eine Messung. Dies ist der terminologische Unterschied, und es ist wichtig: Er meint "Was können Sie rausholen" und ich meine "Was müssen Sie sagen, um es zu simulieren".
@RonMaimon: Das ist komisch. Sie spielen im Grunde die Rolle von Richard Feynman, da er anscheinend nicht davon überzeugt werden konnte, dass P gegen NP ein offenes Problem war; nur bei dir ist es P vs BQP. Ich sage nur, dass ** es noch nicht so oder so bewiesen wurde **. Das heißt nicht, dass ich glaube, dass wir mit Münzwürfen faktorisieren können; Im Gegenteil, ich denke, dass Superpolynomzeit ** wahrscheinlich ** notwendig ist, um Quantencomputer zu simulieren. Aber vieles, was in Quantenzuständen exponentiell ist, ist auch in Wahrscheinlichkeitsverteilungen exponentiell, und wir haben keine soliden Beweise. Stört dich das?
Ich weiß, was Sie sagen, aber dieses Repräsentationsproblem von Quantenzuständen ist das, worauf die Menschen seit 80 Jahren stoßen, dass die Wahrscheinlichkeitsverteilung eine deutliche rechnerische Reduktion aufweist, nämlich Monte-Carlo, und Quantensysteme haben sie nicht. Ich möchte nicht den Eindruck erwecken, dass es da draußen eine clevere Reduzierung gibt, da dies Unsicherheit über die 'tHooft-Threads' schafft, die die Hauptinspiration für diese Frage sind. Es ist in Ordnung zu spekulieren, da wir nicht wissen, wie wir etwas beweisen sollen, aber ich halte Landauer (?) Reversible Berechnung für eine gute Heuristik.
@NieldeBeaudrap: Hör auf! Ich habe darüber nachgedacht, wann ich Jargon-Busting mache, und dies ist ein Fall, in dem es gebraucht wird. Ich werde niemals "nichtdeterministische Maschine" in meinem Leben sagen, ohne sie mit "Parallelmaschine" zu versehen, da ich niemals an der Errichtung von Jargonwänden teilnehmen werde, um Außenstehende fernzuhalten. Diese Art von Dingen hält das Feld der Komplexität im dunklen Zeitalter dauerhaft fest.
@RonMaimon: Ich habe es bearbeitet, weil es polemisch ist. Es ist nicht irreführend, es als "nicht deterministisch" zu bezeichnen: Eine Berechnung mit unbegrenzt vielen Prozessoren ist nur eine Möglichkeit, das Modell zu beschreiben, und * nicht physischer * als eine, die nicht deterministisch vermutet. Sie halten Menschen absichtlich davon ab, die Werkzeuge zu erwerben, die sie benötigen würden, um Komplexitätsliteratur selbst zu bewerten, indem Sie meine Bearbeitung zurücksetzen, die Erklärungen und Links zu den vorhandenen Konzepten enthält. Wenn Sie glauben, dass Komplexität im dunklen Zeitalter liegt, was motiviert Sie überhaupt dazu, sich für NP zu interessieren?
@NieldeBeaudrap: Was meinst du mit "nicht deterministisch raten"? Dies ist die Art von verschleierten Müll, die Menschen in diesem Bereich schreiben. Es gibt keine Möglichkeit, eine "nichtdeterministische Maschine" als etwas "nichtdeterministisches" zu beschreiben. Der Grund für den Namen liegt darin, dass ein Gabelautomat 2 Ausgänge für einen bestimmten Eingang hat und daher eine "nicht deterministische" Entwicklung aufweist. Dies ist eine dumme Konvention, und ich mache sie kaputt. Das Ding klar zu erklären entmutigt nichts, es zeigt nur die Inkompetenz der Menschen. Ich erkläre Dinge einfach, die ihr Leute inkompetent undurchsichtig macht.
@RonMaimon: Eine "nichtdeterministische" Maschine im CS-Sinne ist eine, in der es einen Prozessor gibt, aber * keine * Angabe, welche der zulässigen Übergänge sie untersuchen kann, nicht einmal probabilistisch; es ist einfach * nicht bestimmt *, daher der Name. Es ist nicht physisch, aber dieses Konzept wurde von Logikern definiert, die dem Realismus der physischen Evolution keine Priorität einräumten. Wenn Sie eine andere Sprache bevorzugen, ist das in Ordnung. Dies macht die Standardterminologie jedoch nicht zu "Nicht-Standard". Was unsere Kompetenz oder Verschleierung betrifft: Wenn Sie es geschafft haben, den Stand der Technik zu übertreffen, lassen Sie es uns bitte wissen.
@NieldeBeaudrap: Sie liegen völlig nervig falsch. Die nichtdeterministische Maschine macht alle Übergänge auf einmal. Wenn sie also von Zustand A nach "B und C" gehen kann, geht sie von Zustand A nach Zustand B und Zustand C beide gleichzeitig. Wenn einer der Nachfolgestaaten anhält, wird er angehalten. Deshalb wurde es "nicht deterministisch" genannt, es ist ein dummer Name, es wird von allen anderen "parallel" genannt. Es gibt keinen Stand der Technik zu übertreffen, niemand auf diesem Gebiet hat echte Ergebnisse.
@Ron: abgesehen davon, welche Gründe Sie haben, um maßgebliche Aussagen darüber zu machen, wie Rechenmodelle beschrieben werden und wie sie folglich benannt wurden - wenn der Stand der Technik tatsächlich trivial ist, sollte es auch trivial sein, ihn zu übertreffen. Es ist also ermutigend zu hören, wie Sie das sagen. Gute Fahrt.
@NieldeBeaudrap: Die "Gründe" sind, dass ich durch das Lesen der Definition verstehe, was eine nichtdeterministische Maschine ist. Es ist eine Parallelmaschine, das ist es, es ist keine Debatte möglich. Um Fortschritte zu erzielen, muss man daran arbeiten, und es ist nicht meine Lieblingsbeschäftigung (obwohl ich denke, dass es sehr wichtig ist). Ich habe diese Woche ein bisschen nachgedacht, angespornt von Ihrer Herausforderung, aber ich bin nicht weitergekommen. Ich bin nicht entmutigt, denn das ist so ziemlich das Gleiche wie alle anderen Leute auf diesem Gebiet. Mein Gedankengang ist reversible Berechnung und Verschwendung von Bits. Ich denke, das ist der Schlüssel.
@RonMaimon: sollte in der Tat nicht entmutigend sein, aber es zeigt, dass "Inkompetenz der Mehrheit der Menschen, die an diesem Thema arbeiten" möglicherweise keine experimentell gerechtfertigte Theorie für Stagnation auf diesem Gebiet ist. In Bezug auf die Definitionen beziehen sich diejenigen, die ich kenne, auch nicht auf paralleles Rechnen; Sie beziehen sich auf die Existenz von Rechenzweigen, ohne zu bemerken, wie sie gefunden werden sollten (durch glückliche Vermutungen oder durch Brute-Force-Berechnung). Alles andere ist ein semantischer Glanz. Da solche Maschinen tatsächlich nicht existieren und keine Beschreibung nützlicher ist, gibt es keine Grundlage für eine Widerlegung.
@NieldeBeaudrap: Parallele Maschinen existieren, sie "imaginär" zu nennen, ist dumm. Sie können eine nicht verlangsamte Gabelanweisung auf einer Maschine mit mehreren Prozessoren ausführen, die Leute tun dies jetzt die ganze Zeit, und Sie können sich eine Maschine mit einer großen Anzahl unabhängiger Prozessoren vorstellen. Dies ist, was eine nichtdeterministische Maschine ist, und der Mist, dass sie "unphysisch" oder "mysteriös" ist, ist ärgerlich. Ich habe nicht gesagt, dass die Leute, die auf diesem Gebiet arbeiten, inkompetent sind, ich habe gesagt, dass sie Obskurantisten sind. Es gibt einen großen Unterschied. Logiker sind zum Beispiel kompetente Obskurantisten.
@Ron: Es gibt keine Computer, die möglicherweise die Anzahl der Prozessoren verdoppeln können, die zu einem bestimmten Zeitpunkt an einem Problem arbeiten. Wenn Sie mit der Lösung von Problemen wie SAT auf 30 Bit zufrieden sind, reicht eine Serverfarm mit etwas mehr als einer Milliarde vernetzten einfachen Prozessoren aus, und die Initialisierung dauert mit einer Netzwerktopologie in 3 + 1D nicht allzu lange. Aber es skaliert einfach nicht; Die Struktur der Raumzeit selbst wirkt dem Erhalt der benötigten Ressourcen entgegen. Wenn Sie mit einer festen Anzahl von Prozessoren auskommen, können Sie nicht mehr in Poly-Time fertig werden, es sei denn, z. ** P ** = ** NP **.
@NieldeBeaudrap: Ich verstehe, was Sie meinen - die Rate der Prozessorzuweisung ist zu groß, um physisch zu sein. Aber es ist nicht "unphysisch" wie ein Halteproblem. Ich mag es nicht, wenn die Leute es als unphysisch bezeichnen, es ist einfach "unendlich parallel".
@RonMaimon: würdest du unendliche Energie als unphysisch betrachten? Wenn nicht, warum nicht die Energie, die für eine unendliche Parallelität benötigt wird? Was wäre, wenn wir all diese Energie in einen einzigen Prozessor stecken würden, damit sie unendlich schnell berechnet werden kann (wie bei einem Zeno-Prozessor), um tatsächlich Antworten auf das Problem des Anhaltens zu erhalten? Für mich sind diese Fragen der Unendlichkeit (oder Exponentiale) nicht identisch, aber sie sind sicherlich insofern gleichwertig, als es sich um Ressourcen handelt, mit denen wir niemals hoffen könnten, lokal eine Antwort auf ein schwieriges Rechenproblem zu erhalten. Für mich sind sie alle unphysisch.
@NieldeBeaudrap: Ok, ok, wir sind uns einig, es ist nur eine Frage der "potentiellen Unendlichkeit" und wie Sie die Dinge erklären. Ich mag es nicht, Dinge zu erklären, die einfach sind, damit sie mysteriös klingen - das ist Obskurantismus - und wenn ein Student Sie fragt: "Was ist eine nichtdeterministische Maschine?" Sie können sagen: "Eine Maschine mit so vielen Prozessoren, dass die UNIX-Anweisung 'Fork' kostenlos ist, egal wie oft Sie sie verwenden."
@NieldeBeaudrap: Übrigens führt dies zu einer einfachen Sache, die ich nirgendwo in der Literatur sehe - wenn Sie den Maschinen erlauben, ein Etikett zu führen, das die anderen Prozesse identifiziert, und ihre Ergebnisse mit anderen Maschinen zu tauschen, vergleichen Sie die Notizen, während sie laufen, ich denke du bekommst eine größere Klasse zwischen NP und PSPACE. Lassen Sie mich diese hypothetische Klasse "SHM-P" nennen (für Unix shm --- Shared Memory). Dies ist das natürliche Polynom, das BQP streng einschließt und das nicht PSPACE ist (zumindest nicht offensichtlich).
@RonMaimon: wir konvergieren auf eine ungefähre Vereinbarung; Obwohl Ihre Charakterisierung einer nichtdeterministischen Maschine so wäre, als würde ich ein Elektron als einen winzigen harten Ball elektrischer Ladung beschreiben, der sich um seine Achse dreht, aber für magnetisierte Messgeräte so empfindlich ist, dass er zittert und schwingt, um sich mit oder gegen einen großen Magneten auszurichten Feld, auf das es trifft - es ist eine grobe Beschreibung, die viel verfehlt. Was gekennzeichnete Prozesse betrifft: Das Problem besteht darin, zu definieren, wie die "Prozessoren" Ergebnisse auf eine Weise austauschen würden, die mit der Tensorproduktstruktur übereinstimmt / die Verschränkung berücksichtigt.
@NieldeBeaudrap: Wir konvergieren auf nichts! Ich habe meine Meinung in dieser Diskussion in keiner Weise geändert - Sie sind falsch zu sagen, dass meine Charakterisierung falsch ist, stoppen Sie es, es ist keine grobe Beschreibung, es ist die verdammte Definition! Es ist eine feine Charakterisierung dessen, was eine "nichtdeterministische Maschine" ist. NP ist ein triviales, offensichtliches Konzept. Sie sind falsch in Bezug auf Verschränkung - Sie können den genauen BQP in SHM-P simulieren. Es ist einfach, auf dieser Maschine eine iterierte Matrixmultiplikation durchzuführen. Sie haben nach etwas gefragt, das den Stand der Technik übertrifft, SHM-P ist es.
Drei antworten:
Scott Aaronson
2012-08-21 13:41:46 UTC
view on stackexchange narkive permalink

Dies ist seit 20 Jahren ein großes offenes Problem in der Quantenkomplexitätstheorie. Folgendes wissen wir:

(1) Angenommen, Sie bestehen darauf, nur über Entscheidungsprobleme zu sprechen ("Gesamtprobleme", die für jede Eingabe definiert werden müssen), wie dies bei der Definition von Komplexitätsklassen wie P traditionell der Fall ist , NP und BQP. Dann haben wir Trennungen zwischen BQP und NP im "Black-Box-Modell" (d. H. Dem Modell, bei dem sowohl die BQP-Maschine als auch die NP-Maschine Zugang zu einem Orakel erhalten) nachgewiesen, wie mmc anspielte. Auf der anderen Seite ist es zwar sehr plausibel, dass sich diese auf Orakeltrennungen zwischen BQP und PH (der gesamten Polynomhierarchie) erstrecken, aber wir wissen derzeit noch nicht einmal, wie eine Orakeltrennung zwischen BQP und AM (eine probabilistische Verallgemeinerung) nachgewiesen werden kann von NP etwas höher als MA). Das Beste, was wir tun können, ist, BQP von MA zu trennen.

Und um es noch einmal zu wiederholen: Alle diese Trennungen sind nur im Black-Box-Modell enthalten. Es bleibt selbst auf Vermutungsebene völlig unklar, ob sich diese in Trennungen in der "realen" Welt (d. H. Der Welt ohne Orakel) niederschlagen oder nicht. Wir haben keine klaren Beispiele analog zum Factoring für echte Entscheidungsprobleme in BQP, die plausibel nicht in NP sind. Nachdem ich jahrelang über das Problem nachgedacht habe, habe ich immer noch keine Ahnung, ob BQP in NP in der "realen" Welt enthalten sein sollte oder nicht.

(Anmerkung hinzugefügt: Wenn Sie erlauben "Versprechen Probleme", die Bezeichnung von Informatikern für Probleme, deren Antworten für einige Eingaben undefiniert sein können, dann würde ich vermuten, dass es wahrscheinlich i> tatsächlich eine Trennung zwischen PromiseBQP und PromiseNP gibt. Aber mein Beispiel dafür Ich würde bezeugen, dass die Trennung nur die tautologische ist! Dh "als Eingabe einer Quantenschaltung gegeben, gibt diese Schaltung JA mit einer Wahrscheinlichkeit von mindestens 90% oder mit einer Wahrscheinlichkeit von höchstens 10% aus, versprochen, dass eine davon der Fall ist." ? ")

Weitere Informationen finden Sie in meinem Artikel BQP und der Polynomhierarchie.

(2) Wenn Sie andererseits bereit sind, Ihre Vorstellung von einem "Rechenproblem" über reine Entscheidungsprobleme hinaus zu verallgemeinern - beispielsweise auf Probleme bei der Stichprobe aus einer bestimmten Wahrscheinlichkeitsverteilung -, wird die Situation viel klarer. Erstens, wie Niel de Beaudrap sagte, haben Alex Arkhipov und ich (und unabhängig voneinander Bremner, Jozsa und Shepherd) gezeigt, dass es bei BQP Stichprobenprobleme gibt (technisch gesehen "SampBQP"), die dies nicht können in NP oder irgendwo in der Polynomhierarchie sein, ohne dass die Hierarchie zusammenbricht. Zweitens habe ich in meinem oben verlinkten BQP vs. PH-Artikel bedingungslos bewiesen, dass es in Bezug auf ein zufälliges i> Orakel Stichproben- und Suchprobleme in BQP gibt, die nirgendwo in PH sind, geschweige denn in NP . Und im Gegensatz zu den "seltsamen, speziellen" Orakeln, die für die Trennungen in Punkt (1) benötigt werden, können zufällige Orakel "physikalisch instanziiert" werden - beispielsweise unter Verwendung einer alten kryptografischen Pseudozufallsfunktion - in diesem Fall würden sich diese Trennungen sehr plausibel übertragen in die "reale" Nicht-Orakel-Welt.

"Wir haben keine klaren Beispiele analog zum Factoring für echte Entscheidungsprobleme in BQP, die plausibel nicht in NP sind", akzeptierte ich die Antwort von mmc, weil ich dachte, "rekursive Fourier-Abtastung" sei ein Beispiel dafür. In Bezug auf Orakel und die reale Welt sind NP-Orakel nicht nicht berechenbar, sie sind nur langsam zu berechnen, sodass Sie sie in der realen Welt realisieren können.
Rekursive Fourier-Abtastung ist ein Orakelproblem. Wir wissen nicht, wie wir es in der Nicht-Orakel-Umgebung realisieren sollen. (Außerdem gibt es nur eine Trennung von n gegen n ^ (log n). Wenn Sie eine Trennung von n gegen exp (n) Orakel wünschen, lesen Sie mein BQP gegen PH-Papier.) Und ja, die meisten Orakel, über die wir sprechen about sind berechenbar, aber wenn sie exponentiell langsam sind, kann die Simulation die Komplexitätstrennung zunichte machen, die unser ursprüngliches Ziel war.
mmc
2012-08-20 03:14:41 UTC
view on stackexchange narkive permalink

Es gibt keine endgültige Antwort, da kein Problem innerhalb und außerhalb von P bekannt ist. Es wird jedoch vermutet, dass rekursive Fourier-Abtastung außerhalb von MA liegt ( die probabilistische Verallgemeinerung von NP) und verfügt über einen effizienten Quantenalgorithmus. Weitere Informationen finden Sie auf Seite 3 von dieser Umfrage von Vazirani.

Niel de Beaudrap
2012-08-21 05:13:24 UTC
view on stackexchange narkive permalink

Um die Antwort von mmc zu ergänzen, wird derzeit allgemein vermutet, dass NP und BQP unvergleichbar sind : das heißt, dass keiner im anderen enthalten ist. Wie für die Komplexitätstheorie üblich, sind die Beweise umständlich; und der Verdacht hier ist um Größenordnungen weniger intensiv (wenn wir so tun, als ob die Stärke des Verdachts messbar ist) als die allgemeine Hypothese, dass P ≠ NP .

Insbesondere: Wie Aaronson und Archipov kürzlich gezeigt haben, gibt es Probleme bei BQP , die, wenn sie in NP enthalten wären, implizieren würden, dass die Die Polynomhierarchie kollabiert mit der dritten Ebene. Wenn ich mich darauf beschränke, die Bedeutung dieses Jargons der Komplexitätstheoretiker zu vermitteln, meinen sie jedes Mal, wenn sie über das "Zusammenbrechen der Polynomhierarchie" auf einer beliebigen Ebene sprechen, etwas, das sie als (a) betrachten würden stark> ziemlich unplausibel und folglich (b) katastrophal für ihr Verständnis der Komplexität auf der Ebene des Übergangs von der Newtonschen Mechanik zur Quantenmechanik, dh eine Revolution des Verstehens zu sein informell vorweggenommen vielleicht nicht häufiger als einmal in jedem Jahrhundert oder so. (Die ultimative Krise, ein totaler "Zusammenbruch" dieser "Hierarchie" auf die nullte Ebene, wäre genau das Ergebnis P = NP .)

+1: Das Papier, das Sie verlinken, ist großartig, danke. Übrigens: Zu sagen, wie unplausibel Menschen etwas finden, ist kein Beweis ohne Argument: Man sollte sich einfach ein einfaches, nicht rigoroses Argument ausdenken, um zu erklären, warum Dinge schwierig sind. Es ist einfach für NP und Factoring, aber für die höheren Ebenen der Polynomhierarchie habe ich es nie versucht.
Ron, wenn Sie es versuchen, werden Sie wahrscheinlich ein "einfaches, nicht rigoroses Argument" finden, mit dem Sie sich davon überzeugen können, dass die Polynomhierarchie tatsächlich unendlich sein sollte! (Um zu kalibrieren, bin ich davon viel sicherer als davon, dass Factoring klassisch schwierig ist.) Nehmen Sie einfach die Intuition, die Sie bereits verwendet haben, um sich von P! = NP zu überzeugen, und erweitern Sie sie, um sich von diesem NP zu überzeugen! = coNP. Dann versuchen Sie sich selbst davon zu überzeugen, dass P ^ NP! = NP ^ NP. Schließen Sie dann durch "Physikerinduktion", dass ALLE diese Klassen verschieden sein sollten! :-)
@RonMaimon: Ich stimme Ihnen in Bezug auf die Unplausibilität zu. Ich persönlich bevorzuge tatsächliche Beweise. Natürlich wird erwartet, dass die Beweise (falls vorhanden) schwer zu finden sind, da es noch niemandem gelungen ist. Ich vertrete wirklich nur die gesellschaftspolitische Bedeutung dieser Behauptungen.
@ScottAaronson: Die Intuition, die ich verwende (die möglicherweise auf irgendeine Weise rigoros gemacht werden könnte), basiert auf der minimalen Anzahl von Abfallbits während einer reversiblen Berechnung, und wenn Sie ein NP-Orakel einführen, wie in höheren Ebenen der Heirarchie, müssen Sie Berechnen Sie den Orakelwert und diese Abfallbits werden nicht auf einfache Weise gezählt, sodass ich die Heuristik nicht sofort ausführen kann. Es ist wahrscheinlich einfach zu beheben. Diese Heuristik ist besser als die Heuristik, die ich in der Literatur sehe. Ich habe versucht, sie einmal zu beweisen, aber es ist schwierig, die Minimalität von Abfallstücken in einer reversiblen Implementierung zu beweisen.
... um sich selbst davon zu überzeugen, dass Factoring schwierig ist, sollten Sie die minimale Anzahl von Bits in einer reversiblen Berechnungsimplementierung von Multiplizieren berücksichtigen. Dann ist mit Sicherheit eine vollständige Suche über diese Bits erforderlich, und es gibt genügend Abfallbits, um Ihnen mitzuteilen, dass das Problem schwierig ist.
Ron, ich verstehe dein Argument nicht ganz, warum Factoring schwierig sein sollte, aber es scheint, dass es unmöglich funktionieren kann. Wie geht Ihr Argument mit der Existenz von Algorithmen wie dem Zahlenfeldsieb um, das eine n-Bit-Ganzzahl klassisch mit ~ exp (n ^ {1/3}) Schritten faktorisiert, immer noch exponentiell, aber viel schneller als eine "vollständige Suche" "? Beachten Sie, dass das Zahlenfeldsieb wie jeder Algorithmus mit nur einer Verlangsamung des konstanten Faktors reversibel implementiert werden kann.
@RonMaimon: Können Sie skizzieren, wie Ihre Abfallanalyse mit einem effizient lösbaren Problem wie 2-CNF-SAT ablaufen würde?
@ScottAaronson: Die Anzahl der Abfallbits ist für das Factoring nicht so groß, sie skaliert nicht linear mit der Anzahl der Bits. Sie müssen den Informationsverlust bei der Multiplikation kennen. Ich vergesse, was die richtige Skalierung ist, die ich vor Jahren gemacht habe, aber ich erinnere mich, dass es schwer herauskommt, aber nicht vollständig exponentiell schwer. Ich könnte es ein bisschen reproduzieren, aber ich habe eine Weile nicht mehr darüber nachgedacht.
@NieldeBeaudrap: Die Idee ist, dass die Vorwärtsberechnung von 2-sat nicht viele Abfallbits benötigt. Sie können sie mit einer Anzahl von Abfallbits implementieren, die nur als Protokoll skaliert werden, und dies können Sie an der Lösung des Rückwärtsproblems erkennen. Ich erinnere mich ehrlich gesagt nicht an die Details, ich habe es vor langer Zeit getan.
Das klingt entweder * viel * zu gut, um wahr zu sein - als würde Ihre "Methode zum Zählen von Abfallbits" die theoretische Informatik revolutionieren, indem sie uns zumindest heuristische Antworten auf alle großen ungelösten Probleme gibt - oder als hätten Sie einfach welche Möglichkeit, die bekanntesten konventionellen Algorithmen in dieses Framework abzubilden. Also ja, Details bitte! (Da es ein bisschen vom Thema abweicht, posten Sie sie woanders oder senden Sie mir und Niel eine E-Mail.)
@RonMaimon: ebenso jeder Satz von Scotts vorherigem Kommentar.
@Ron: Da ich durch das Lesen Ihrer Physik-SE-Beiträge viel gelernt habe, finde ich es traurig, dass Sie verärgert auf das reagieren würden, was zumindest meinerseits (und ich stelle mir Niels vor) eine echte Bitte um Erklärung für etwas war Das klingt ehrlich gesagt unglaublich für Leute, die auf diesem Gebiet arbeiten. (In der Geschichte von CS gibt es viele falsche Behauptungen darüber, welche Algorithmen aus heuristischen Gründen "offensichtlich nicht verbesserbar" waren!) Da Sie Fragen wollten, sind hier einige: Sagt Ihnen Ihre heuristische Methode, wie komplex das Problem des Graphisomorphismus tatsächlich sein sollte? ? Wie wäre es mit Matrixmultiplikation?
@RonMaimon: In Bezug auf Junk-Argumente erzähle ich Ihnen nur, wie (andere) Leute über Dinge sprechen: Ich bin weder aktiv noch Experte in der Polynomhierarchie. Ich bin verwirrt, dass Sie so wütend auf die Intuitionen anderer Menschen sein sollten (nicht Ihre oder im Übrigen meine), wenn Sie einen solchen Speicher eindeutig auf Ihre eigene Weise platzieren, um sie zu generieren, dass Sie meine Kontrapunkte als falsche Darstellung abtun. Gibt es einen Modus, in dem wir kommunizieren können, in dem ich vermeiden kann, Sie falsch zu bürsten, in den Fällen, in denen wir beide etwas zu sagen haben, in denen "Wissen" zu "Ideenfindung" führt?
@ScottAaronson: Ich habe meinen lächerlichen Kommentar gelöscht und es tut mir wirklich leid. Ich hatte eine grenzüberschreitende psychotische paranoide Reaktion. Ich könnte voller Mist sein, ich erinnere mich nicht sehr gut an das Argument, und ich habe es nie auf andere spezifische Probleme als das Factoring angewendet. Die Idee ist, die Anzahl der Abfallbits in einer reversiblen Implementierung des einzigen NP-Problems zu untersuchen, das mir wichtig war - den anfänglichen Speicherzustand eines Universalcomputers anhand der Anweisung und des endgültigen Speicherzustands herauszufinden. Dies ist offensichtlich der Urvater aller anderen NP-vollständigen Probleme.
@NieldeBeaudrap: Ich entschuldige mich auch bei Ihnen, meine Reaktion war inakzeptabel und ich habe sie gelöscht. (Fortsetzung) "Herausfinden eines Startzustands aus dem Endzustand" ist auf einem irreversiblen Computer offensichtlich NP-vollständig. Auf einem reversiblen Computer ist dies trivial. Sie führen den Computer nur in umgekehrter Reihenfolge aus. Die Idee war also, dass Sie die Junk-Bits verfolgen, die für die irreversible Berechnung weggeworfen werden, und diese minimieren. Dies gibt Ihnen die Entropie des zukünftigen Problems. Die Intuition, die ich hatte, war, dass die optimale Umkehrentropie das Protokoll der Größe des Suchraums ist, wenn ich rückwärts gehe.
... Ich nahm an, dass dies die Intuition aller auf dem Gebiet war, warum NP-Komplettprobleme schwierig waren. Ich kann nichts direkt über Entscheidungsprobleme sagen, weil ich darüber nachgedacht habe, einen Anfangszustand in einen Endzustand zu bringen, nicht ein bisschen. Es gibt ein großes Problem bei der Argumentation, dass Sie möglicherweise viele Kopien des Problems gleichzeitig reversibel parallel berechnen und Abfallbits gemeinsam nutzen müssen, um die Entropieproduktion der Berechnung auf die gleiche Weise wie Shannons Entropie zu minimieren wird nur auf Kopien gefunden. Es ist wirklich halbherzig, daher meine defensive psychotische Antwort.
Vielen Dank; Entschuldigung dankbar angenommen! Ich war dort, Mann: Als ich ein Student war, dachte ich auch, ich sollte alles ignorieren, was über P vs. NP geschrieben wurde, und den "richtigen" Weg finden, um die Komplexitätstheorie von Grund auf neu zu betrachten. Aber wiederholte Erfahrungen nach dummen Sackgassen, der Neuerfindung des Rades usw. fuhren schließlich nach Hause, dass die Leute, die zuvor über diese Dinge nachgedacht hatten, nicht alle Dummköpfe waren. Übrigens ist das Lustige an NP-vollständigen Problemen natürlich, dass per Definition * jedes * NP-vollständige Problem der "Großvater" aller anderen ist!
@ScottAaronson: Wenn Sie nicht genau die gleiche Idee hatten, die ich in Bezug auf reversible Abfallbits hatte, waren Sie nicht dort, Sie machen eine Analogie. Neuerfindung ist wichtig, aber dies ist kein Beispiel. Es ist nicht im Sinne der Idee, dass "jedes NP-Problem zum Großvater wird", weil sie es nur sind, weil Cook gezeigt hat, dass sie dem von mir gegebenen Problem entsprechen. Ich denke nicht, dass die Leute, die dies studieren, Dummköpfe sind, es ist nur völlig klar, dass sie absolut nicht den geringsten Hinweis auf eine Idee haben, wie man etwas beweisen kann, nicht einmal ein heuristisches Argument. Also habe ich mir einen ausgedacht.
@ScottAaronson: Außerdem hat das Feld im Wesentlichen eine echte Idee - relativieren Sie sich zu einem Orakel - und so verdienen Sie Geld und erhalten Positionen im Feld. Dies bedeutet, dass die meisten Artikel in geistesgestörtem, hirnzerstörendem Jargon und undurchdringlicher Strenge vergraben sind und einfache Beschreibungen von CS-Algorithmen vermeiden. Die meisten Artikel, die ich sehe, sind Umschreibungen eines Ansatzes auf tausend leicht unterschiedliche Arten (es gibt natürlich Ausnahmen). Ich finde es aus diesem Grund schwierig, diese Literatur zu lesen. Es ist wie eine Leselogik, die im Vergleich zu Papieren auch einen Mangel an Ideen aufweist.
Erstens: Ich spreche Ihre Idee nicht an, weil ich sie nicht verstehe. Warum sollten wir erwarten, dass die Begrenzung der Anzahl von Abfallbits in einer reversiblen Berechnung (anstelle einer anderen Größe wie der Anzahl von Gates oder der Anzahl von Speicherbits in einer * irreversiblen * Berechnung) einen bestimmten Einblick gibt? Schreiben Sie etwas detaillierteres auf, und ich werde es gerne lesen und mir eine Meinung bilden.
@ScottAaronson: Da Sie die Berechnung beginnend mit _any Abfallbits_ umkehren können, indem Sie den Computer rückwärts ausführen, und nur wenn Sie den richtigen Endwert der Abfallbits erraten haben, werden Sie sie alle auf Null setzen, wenn Sie mit dem Umkehren fertig sind. Wenn Sie versuchen, so wenig Abfallbits wie möglich zu verwenden, sollten Sie diese beim Berechnen maximal komprimieren. Dann werden sie effektiv zufällig (andernfalls könnten Sie sie weiter komprimieren), sodass die verbleibende Abfallbitanzahl die minimale Schwierigkeit ist - einen Teil der Vorwärtsberechnung zu erraten.
Zweitens: Ich würde sagen, Ihre Einschätzung des Zustands der Komplexitätstheorie ist um 1975 ziemlich genau. Heute * haben * wir nicht relativierende Ergebnisse, von IP = PSPACE und dem PCP-Theorem bis zu Williams 'NEXP vs. ACC-Durchbruch im letzten Jahr bis Mulmuleys GCT-Programm. Kennen Sie diese? Sie sind alle noch weit von P! = NP entfernt, aber das ist die falsche Metrik: Sie verwenden ganz offensichtlich nicht triviale neue Ideen, um schwierige Komplexitätsfragen zu beantworten, die die Leute vorher nicht beantworten konnten. Sie zu verwerfen ist wie die Stringtheorie zu verwerfen, weil sie uns der Erklärung der Myonenmasse nicht näher gebracht hat.
(In ähnlicher Weise finde ich HEP-Papiere voller geistesgestörter, hirnzerstörender Fachsprache und undurchdringlicher Handbewegung! Darf dort nicht zu viel Verständnis wert sein ...)
@ScottAaronson: Ich kenne diese nicht, danke, dass Sie darauf hingewiesen haben! Ich freue mich zu lernen und hoffe, dass die Ideen gut sind. Die Analogie zu HEP ist nicht wirklich richtig. Die Physiker beugen sich im Allgemeinen nach hinten, um unnötigen Jargon zu beseitigen, und sprechen so viel wie möglich in heimeligen Metaphern. Es gibt eine politische Kabale in der Physik, die Sie schlagen wird, wenn Sie die Dinge nicht so klar wie möglich sagen. Es ist sehr schön, und ich wünschte, andere Bereiche hätten es.
Lassen Sie mich sehen, ob ich Ihre Idee verstehe: Zuerst reparieren Sie eine "universelle" reversible Schaltung C? (Woher wissen Sie sonst, welche reversible Berechnung rückwärts ausgeführt werden muss, wenn Sie die Endwerte der Abfallbits erraten haben?) Wenn Sie dann (sagen wir) eine zusammengesetzte Ganzzahl N und ihre Primfaktoren p, q gegeben haben, suchen Sie nach einem Endwert Wert b der Abfallbits, so dass C ^ {- 1} (p, q, b) = (N, a) für eine andere Zeichenfolge a (die Sie sich als "Anweisungen" für C vorstellen können)? Selbst wenn Sie eine solche gefunden haben, gibt es natürlich keine Garantie dafür, dass sie für eine * andere * zusammengesetzte Ganzzahl N 'funktioniert.
Es ist erstaunlich, wie stark die Wahrnehmung von "Jargon-Ness" durch die Menschen nur ihren Hintergrund widerspiegeln kann. Ich hatte gehört, wie wichtig AdS / CFT ist, also ging ich die Artikel durch und hoffte, die neuen konzeptionellen Erkenntnisse über die Raumzeit in der Quantengravitation zu erhalten ... und fand stattdessen technische Konstruktionen mit Stapeln von D3-Branen. Welche CS-Theoriepapiere lesen Sie? Was auch immer sie sind, ich kann Sie wahrscheinlich auf bessere hinweisen. In den Proceedings der großen CS-Theoriekonferenzen (STOC, FOCS, CCC, ...) sind die ersten Seiten jedes Papiers nur Geschichte, Motivation, hochrangige Ideen ...
@ScottAaronson: Nicht genau --- Sie beginnen mit einem reversiblen Computer und geben (I, p, q, 0) ein, wobei 0 eine Folge von auf Null gesetzten Bits ist. Ich bin die Anweisung zum Multiplizieren (die Sie nicht berühren) und p und q sind die Eingänge. Dann lässt du es vorwärts laufen und bekommst (I, pq, J), wo J Müll ist. Sie ignorieren jetzt J und erhalten die Ausgabe der regulären Maschine: (I, pq). Wenn Sie der Antwort nur Bits hinzufügen, kehren Sie die zu berechnende Berechnung um (I, p ', q', J '). Wenn Sie richtig geraten haben, ist J '0, wie Sie die Maschine ursprünglich initialisiert haben. Wenn Sie den am wenigsten verschwenderischen Algorithmus erstellen (möglicherweise auf Kopien), mussten Sie nach J. suchen.
@ScottAaronson: In Bezug auf Jargon und Physik sind die jargonfreien Erkenntnisse zur Holographie besser in den Arbeiten von 'tHooft in Nuclear Physics B im Zeitraum 1985-1990 zu finden, enthalten jedoch einige Ungenauigkeiten. Die Susskind-Papiere von '90 -96 enthalten auch diese Erkenntnisse. Das Maldacena-Papier baut etwas auf früheren String- und Supergravity-Papieren auf und ist weniger zugänglich.


ⓘ
Diese Fragen und Antworten wurden automatisch aus der englischen Sprache übersetzt.Der ursprüngliche Inhalt ist auf stackexchange verfügbar. Wir danken ihm für die cc by-sa 3.0-Lizenz, unter der er vertrieben wird.
Loading...