Probleme mit großen offenen Komplexitätslücken

32

Bei dieser Frage geht es um Probleme, bei denen eine große Lücke in Bezug auf die Komplexität zwischen der bekannten Untergrenze und der Obergrenze besteht, jedoch nicht aufgrund offener Probleme in Bezug auf die Komplexitätsklassen.

Um genauer zu sein, nehmen wir an, ein Problem hat die Lückenklassen (mit , nicht eindeutig definiert), wenn eine maximale Klasse ist, für die wir beweisen können, dass es -hart ist, und eine minimale bekannte obere Klasse ist gebunden, dh wir haben einen Algorithmus in , der das Problem löst. Dies bedeutet, wenn wir am Ende feststellen, dass das Problem vollständig mit , hat dies keinen Einfluss auf die Komplexitätstheorie im Allgemeinen, anstatt einen Algorithmus für ein vollständiges Problem zu finden.A,BABAABBCACBPNP

Ich interessiere mich nicht für Probleme mit und , weil es bereits Gegenstand dieser Frage ist .APB=NP

Ich suche nach Beispielen für Probleme mit Lückenklassen, die so weit wie möglich sind. Um den Umfang und die Frage zu präzisieren, interessiere ich mich besonders für Probleme mit und , was bedeutet, dass sowohl die Mitgliedschaft in als auch die Vollständigkeit mit dem aktuellen Kenntnisstand übereinstimmt, ohne dass bekannt wird, dass Klassen zusammenbrechen (sagen wir Klassen aus diese Liste ).APBEXPTIMEPEXPTIME

Denis
quelle
Was meinst du mit Klassen eines Problems? Angenommen, das Problem ist SAT. Wie definieren Sie Klassen?
RB
SAT ist NP-vollständig, daher können wir und es gibt hier keine Lücke, da die Komplexität von SAT genau einer bereits bekannten Klasse entspricht. Es wäre ein Durchbruch in der Komplexitätstheorie, ein neues Ergebnis zur Komplexität von SAT zu zeigen (nämlich zu einer kleineren Klasse zu gehören). Zugegeben, die Frage ist nicht vollständig definiert, da es darauf ankommt, welche Komplexitätsklassen als "Mainstream" betrachtet werden und nicht eindeutig definiert sind. Die spezifische Frage ist jedoch klar definiert: Beispiele für Sprachen, für die es nach dem derzeitigen Kenntnisstand möglich ist, dass sie in P oder EXPTIME-complete vorliegen. A , BA=B=NPA,B
Denis
eigentlich immer noch nicht ganz klar definiert, da "nicht kollabiert", also beruht es auf dem begriff "bekannte klasse". Offensichtlich entspricht ein PSPACE-vollständiges Problem nicht den Anforderungen, obwohl es mit dem aktuellen Wissensstand vereinbar ist, P oder EXPTIME-complete zu verwenden. Diese Liste kann beispielsweise als Referenz für eine "bekannte" Klasse verwendet werden: en.wikipedia.org/wiki/List_of_complexity_classes
Denis
13
Es entspricht nicht ganz Ihrer spezifischen Fragestellung, aber die existenzielle Theorie der Realitäten widersteht allen Anschein nach jeder weiteren Klassifizierung, die über NP-hart und innerhalb von PSPACE hinausgeht (das letztere Ergebnis stammt von JF Canny aus dem Jahr 1988). en.wikipedia.org/wiki/Existential_theory_of_the_reals
Anemone

Antworten:

28

Das Knotenäquivalenzproblem .

Sind zwei in der Ebene gezogene Knoten topologisch gleich? Es ist bekannt, dass dieses Problem entscheidbar ist, und es scheint keine Hindernisse für die Komplexität der Berechnung in P zu geben. Die beste Obergrenze, die derzeit für die Komplexität der Zeit bekannt ist, scheint ein Turm mit s Höhe c n zu sein , wobei c = 10 10 6 und n ist die Anzahl der Kreuzungen in den Knotendiagrammen. Dies ist auf die von Coward und Lackenby festgelegte Anzahl von Reidemeister-Zügen zurückzuführen, die erforderlich sind, um einen Knoten zu einem äquivalenten Knoten zu machen. Siehe Lackenbys neueres Papier2cnc=10106n für einige neuere verwandte Ergebnisse und für die explizite Form der oben angegebenen Bindung (Seite 16).

Peter Shor
quelle
Vielen Dank für Ihre Antwort. Kennen Sie die aktuellen Grenzen? Können Sie auf eine Referenz verweisen, die den aktuellen Stand der Technik wiedergibt? Ich habe Probleme, eine klare zu finden.
Denis
Ich habe unterwegs zu finden , etwas jünger als die 1998 Papier von Hass, Lagarias und Pippenger versucht hier . Dies besagt, dass das Knotenäquivalenzproblem bekanntermaßen entscheidbar ist. Ich wäre nicht überrascht, wenn jemand gezeigt hätte, dass es seitdem EXPTIME ist, aber ich glaube nichts Besseres als das, was bekannt ist, und es ist sicher nicht klar, dass es nicht P ist. Ich bin mir ziemlich sicher, dass es keines ist von den Ergebnissen, die zeigen, dass die Entscheidung, ob etwas geknüpft ist, in NP liegt, erstreckt sich auf dieses allgemeinere Problem.
Peter Shor
Diese MO-Frage steht im Zusammenhang mit: mathoverflow.net/questions/77786/…. Unter Verwendung der jüngsten Ergebnisse, die von Lackenby in people.maths.ox.ac.uk/lackenby/ekt11214.pdf angekündigt wurden , erhält man die für jeden Knoten Typ K, Bestimmen, ob ein gegebener Knoten K entspricht, ist in NP (beachten Sie, dass dies das Knotenäquivalenzproblem nicht verbessert)
Arnaud
@Arnaud: Tatsächlich scheint es mir, als ob diese Ergebnisse beweisen, dass für zwei Diagramme mit höchstens n Kreuzungen das Knotenäquivalenzproblem höchstens für einen Turm mit 2 der Höhe , bei dem c eine enorme Konstante ist, rechtzeitig gelöst werden kann . Ich sollte dies überprüfen und meine Antwort bearbeiten. cnc
Peter Shor
@ PeterShor Ja in der Tat. Ich habe mich auf das neuere Ergebnis konzentriert, da es bei Veröffentlichung zu einer verbesserten Schranke führen kann, wenn das eigentliche Polynom erklärt wird.
Arnaud
23

Hier ist eine Version des MCSP-Problems (Minimum Circuit Size Problem): Hat die Bit-Wahrheitstabelle einer Booleschen Funktion eine Schaltung mit einer Größe von höchstens 2 n / 2 ?2n2n/2

Bekanntermaßen nicht in . Enthalten in N P . Es wird allgemein angenommen, dass es N P -hart ist, aber dies ist offen. Ich glaube, es ist nicht einmal bekannt, dass es A C 0 [ 2 ] -hart ist. In der Tat zeigt die jüngste Arbeit mit Cody Murray (erscheint in CCC'15), dass es keine einheitliche NC0-Reduktion von PARITY zu MCSP gibt.AC0NPNPAC0[2]

Ryan Williams
quelle
23

Die Komplexität der Berechnung eines Bits (in Binärform angegeben) einer irrationalen algebraischen Zahl (z. B. ) hat die beste bekannte obere Grenze für P P P P P P P über eine Reduktion auf das Problem B i t S L P , welche diese obere Grenze zu habenbekannt[ABD14]. Andererseits wissen wir nicht einmal, ob dieses Problem schwieriger ist als die Berechnung der Parität vonnBits -soweitwir wissen, könnte dieses Problem inA C 0 liegen . Beachten Sie jedoch, dass wir wissen, dass kein endlicher Automat die Bits einer irrationalen algebraischen Zahl berechnen kann[AB07]2PPPPPPPBitSLPnAC0

SamiD
quelle
21

Ein weiteres natürliches topologisches Problem, das der Antwort von Peter Shor ähnelt, ist die Einbettbarkeit von zweidimensionalen abstrakten simplizialen Komplexen in R3 . Im Allgemeinen ist es natürlich zu fragen, wann wir effektiv / effizient entscheiden können, dass ein abstrakter dimensionaler simplizieller Komplexk in eingebettet werden kann . Für k = 1 und d = 2 ist dies das Graphplanaritätsproblem und hat einen linearen Zeitalgorithmus. Für k = 2 und d = 2 gibt es auch einen linearen Zeitalgorithmus . DasRdk=1d=2k=2d=2 Fall k = 2 , d = 3 war bis zum letzten Jahr offen, alsMatousek, Sedgwick, Tancer und Wagner zeigten, dass er entscheidbar ist. Sie sagen, dass ihr Algorithmus eineprimitive rekursiveZeitgrenze hat, abergrößer als ein Turm von Exponentialen ist. Andererseits spekulieren sie, dass es möglich sein könnte, das Problem in NP umzusetzen, aber darüber hinauszugehen, wäre eine Herausforderung. Es scheint jedoch keinen starken Beweis dafür zu geben, dass ein Polyzeit-Algorithmus unmöglich ist.k=2d=3

Das letztgenannte Papier enthält viele Literaturhinweise.

Sasho Nikolov
quelle
16

Multicounter-Automaten (MCAs) sind endliche Automaten, die mit Zählern ausgestattet sind, die in einem Schritt inkrementiert und dekrementiert werden können, aber nur Ganzzahlen> = 0 als Zahlen verwenden. Im Gegensatz zu Minsky-Maschinen (auch Zählerautomaten genannt) dürfen MCAs nicht testen, ob ein Zähler Null ist.

Eines der algorithmischen Probleme mit einer großen Lücke im Zusammenhang mit MSCs ist das Problem der Erreichbarkeit. ZB, ob der Automat aus einer Konfiguration mit dem Ausgangszustand und allen Zählern Null, einer Konfiguration mit einem akzeptierenden Zustand und allen Zählern wieder Null erreichen kann.

Das Problem ist schwer für EXPTIME (wie von Richard Lipton 1976 gezeigt), entscheidbar (Ernst Mayr, 1981) und lösbar in Fω3 (danke Sylvain, dass er darauf hingewiesen hat). Eine riesige Lücke.

Thomas S
quelle
3
Hallo Thomas, es gibt eine Behauptung einer expliziten (und höchstwahrscheinlich nicht engen) Komplexitätsobergrenze in einem kürzlich erschienenen arXiv-Artikel: arxiv.org/abs/1503.00745 . Die vorgeschlagene Obergrenze in liegt jedoch weit über den Komplexitätsklassen, an denen das ursprüngliche Poster interessiert war.Fω3
Sylvain
@ Sylvain Cool! Vielen Dank für das Teilen. :)
Michael Wehar
@ Sylvain Ist EXPTIME die bekannteste Untergrenze?
Michael Wehar
2
@Michael: Die beste Untergrenze für das Entscheidungsproblem ist tatsächlich EXPSPACE (Lipton, 1976, cpsc.yale.edu/sites/default/files/files/tr63.pdf ). Der Algorithmus von Mayr (1981, dx.doi.org/10.1145/800076.802477 ), Kosaraju (1982, dx.doi.org/10.1145/800070.802201 ) und Lambert (1992, dx.doi.org/10.1016/0304- 3975 (92) 90173-D ) analysiert , in dem genannten arXiv Papier bekannt ist , zumindest erfordern Ackermannian (dh ) Zeit. Fω
Sylvain
@ Sylvain Vielen Dank für all die zusätzlichen Informationen. Ich weiß das wirklich zu schätzen. :)
Michael Wehar
11

(Quantum Merlin-Arthur mit zwei nicht verwickelten Beweisen): sicherlich Q M A -hart, aber nur in N E X P bekannt . QMA(2)QMANEXP

Martin Schwarz
quelle
9

Das mit Noethers Normalisierungs-Lemma verbundene Rechenproblem für explizite Varietäten ("explizit" im Sinne dieses Papiers [ frei verfügbare Vollversion ]). Die bekannteste obere Schranke ist (Anmerkung, LEERTASTE, nicht ZEIT!), Aber es wird vermutet, dass sie sich in P befindet (und in der Tat ist ihr Vorhandensein in P im Wesentlichen gleichbedeutend mit dem Derandomisieren von PIT).EXPSPACEPP

Joshua Grochow
quelle
Können Sie diesbezüglich weitere Informationen in expliziter Form bereitstellen? sieht aus wie eine Art bpp-vollständiges Problem?
@Arul: Weder PIT noch dieses Problem sind in irgendeiner mir bekannten Weise BPP-vollständig. (Tatsächlich ist der Nachweis, dass BPP-vollständige Probleme bestehen, noch offen und erfordert nicht-relativierende Techniken - ein Ergebnis, das auf Sipser zurückgeht.) Die Derandomisierung hat jedoch einen Kompromiss zwischen Härte und Zufälligkeit, da ihre Derandomisierung im Wesentlichen äquivalent ist Grenzen zu senken. Abgesehen von dem in der Antwort verlinkten Artikel ("GCT 5"), Lookup-Härte-Zufälligkeit und Kabanets-Impagliazzo.
Joshua Grochow
Ich werde das tun , aber ich war in diesem Satz interessiere ‚und in der Tat, in P sein Sein ist im wesentlichen äquivalent zu derandomizing PIT‘ , der PIT zu sagen scheint , ist eine Art Proxy - vollständigen Problem
@Arul: Ja, um zu sehen, warum PIT so ein "Proxy-vollständiges Problem" ist, lesen Sie die Dinge, auf die ich in meinem vorherigen Kommentar verwiesen habe.
Joshua Grochow
Warum verwendet er in vielen seiner Werke "Sri Ramakrishna gewidmet"?
6

Das Skolem-Problem (bei einer linearen Wiederholung mit ganzzahligen Basisfällen und ganzzahligen Koeffizienten erreicht es jemals den Wert 0) ist bekanntermaßen NP-hart und nicht als entscheidbar bekannt. Soweit ich weiß, würde irgendetwas dazwischen mit unserem aktuellen Wissen übereinstimmen, ohne dass die Standardkomplexitätsklassen zusammenbrechen.

David Eppstein
quelle