Größere ungelöste Probleme in der theoretischen Informatik?

218

Wikipedia listet unter "ungelöste Probleme in der Informatik" nur zwei Probleme auf :

Was sind andere Hauptprobleme, die zu dieser Liste hinzugefügt werden sollten?

Regeln:

  1. Nur ein Problem pro Antwort
  2. Geben Sie eine kurze Beschreibung und relevante Links an
Shane
quelle
1
Da Sie nach einer Liste fragen und es keine einzige Antwort gibt, funktioniert dies möglicherweise besser, wenn Sie als Community-Wiki gekennzeichnet sind.
Daniel Apon
2
Ein ungelöstes Problem pro Antwort, bitte; dann können wir die Antworten einfach nach oben / unten ordnen!
Jukka Suomela
15
Warum entsteht nur Komplexität? TCS bietet mehr als nur Komplexität! Keine offenen typentheoretischen Probleme? Programmiersprachen?
Jacques Carette
3
füge sie hinzu, Jacques :).
Suresh Venkat
8
Ich denke, wir sollten zwischen großen offenen Problemen, die als grundlegende Probleme angesehen werden, wie , und großen offenen Problemen, die einen technischen Durchbruch darstellen, wenn sie gelöst werden, aber nicht unbedingt als grundlegende, z. B. exponentielle untere Schranken von A, unterscheiden C 0 ( 6 ) -Schaltungen (dh Gatter). Deshalb sollten wir möglicherweise ein neues Community-Wiki mit dem Titel "offene Probleme in den Grenzen von TCS" oder ähnliches eröffnen. PNPAC0(6)AC0+mod6
Iddo Tzameret

Antworten:

137

Kann die Multiplikation von mit Matrizen in -Operationen durchgeführt werden?n O ( n 2 )nnO(n2)

Der Exponent der bekanntesten oberen Schranke hat sogar ein spezielles Symbol, . Derzeit beträgt nach dem Coppersmith-Winograd-Algorithmus ungefähr 2,376 . Eine schöne Übersicht über den Stand der Technik gibt Sara Robinson, Auf dem Weg zu einem optimalen Algorithmus für die Matrixmultiplikation , SIAM News, 38 (9), 2005.ωωω

Update: Andrew Stothers (in seiner Arbeit von 2010 ) zeigte, dass , das von Virginia Vassilevska Williams (in einem Preprint vom Juli 2014 ) auf . Diese Grenzen wurden beide durch eine sorgfältige Analyse der grundlegenden Kupferschmied-Winograd-Technik erhalten.ω < 2,372873ω<2.3737ω<2.372873

Weitere Aktualisierung (30. Januar 2014): François Le Gall hat bewiesen, dass in einem in der ISSAC 2014 veröffentlichten Artikel ( arXiv preprint ) enthalten ist.ω<2.3728639

András Salamon
quelle
Wie wäre es mit einem bescheidenen und realistischen Ziel von oder einer anderen Funktion zwischen und ? Schließlich wird erwartet, dass die ganzzahlige Multiplikation die Untergrenze von . n 2 + n 2 O ( n log n )O(n2logn)n2+ϵn2O(nlogn)
Mitch
Ich bin mir nicht sicher, ob es ein "bescheidenes und realistisches Ziel" ist, von auf zu , geschweige denn auf unter . Aber es wäre großartig, einige Fortschritte zu sehen, also probieren Sie es aus! 2 + 2 + 2+0.3762+ϵ2+ϵ
András Salamon,
13
Der Matrixmultiplikations-Exponent ist definiert als die kleinste reelle Zahl so dass arithmetische Operationen für alle ausreichen . Wahrscheinlich sollte ein Faktor wie erwartet werden. O ( n ω + ε ) ε > 0 log nωO(nω+ϵ)ϵ>0logn
Zeyu,
2
Der Vollständigkeit halber nur das aktuelle Wissen hinzufügen, dass CW-gebunden vor ein paar Tagen von Virginia Williams verbessert wurde. Und wie viele andere in der Gemeinde bemerkten, hatte Andrew Stothers etwa ein Jahr vor Virginia seine gebundenen CWs erhalten. Der aktuelle Rekord istO(n2.373)
Akash Kumar
123

Ist der Graph-Isomorphismus in P?

Die Komplexität des Graph Isomorphism (GI) ist seit mehreren Jahrzehnten eine offene Frage. Stephen Cook erwähnte es 1971 in seiner Arbeit über die NP-Vollständigkeit von SAT .

Das Bestimmen, ob zwei Graphen isomorph sind, kann normalerweise schnell erfolgen, beispielsweise durch Software wie nautyund saucy. Andererseits konstruierte Miyazaki Klassen von Instanzen, für die nautynachweislich exponentielle Zeit erforderlich ist.

Read und Corneil besprachen die zahlreichen Versuche, die Komplexität von GI bis zu diesem Punkt in den Griff zu bekommen : The Graph Isomorphism Disease , Journal of Graph Theory 1 , 339–363, 1977.

Es ist nicht bekannt, dass GI im co-NP vorliegt, aber es gibt ein einfaches randomisiertes Protokoll für den Graph Non-Isomorphism (GNI). Es wird daher angenommen, dass GI (= co-GNI) nahe an NP co-NP liegt.

Wenn GI hingegen NP-vollständig ist, kollabiert die Polynomialhierarchie. Daher ist es unwahrscheinlich, dass GI NP-vollständig ist. (Boppana, Håstad, Zachos, Hat co-NP kurze interaktive Beweise?, IPL 25 , 127–132, 1987)

Shiva Kintali hat in seinem Blog eine nette Diskussion über die Komplexität von GI.

Laszlo Babai hat bewiesen, dass der Graphisomorphismus in subexponentieller Zeit vorliegt .

András Salamon
quelle
Bitte schauen Sie sich auch diesen Eintrag an.
MS Dousti
Ich habe eine genaue Untergrenze für die generische Brute-Force-Automorphismus-Erkennung festgelegt. oeis.org/A186202 Viel weniger alsaber immer noch exponentiell. In der Hoffnung, dass McKay es mit den Schrier-Sims für seine neueste NAUTY-Inkarnation koppeln wird, damit es auf paralleler Hardware ausgeführt werden kann. n!
Chad Brewbaker
1
Babai widerrief die Behauptung der quasipolynomialen Laufzeit . Anscheinend gab es einen Fehler in der Analyse.
Raphael
4
Der Anspruch wurde wiederhergestellt: people.cs.uchicago.edu/~laci/update.html
Uhr
91

Komplexität des Factorings

Ist Faktorisierung in ?P

Kaveh
quelle
Gibt es gute Veröffentlichungen, die die Komplexität von Factoring oder Primalitätstests im Hinblick auf die Struktur der Halbgruppe der Additions- und Multiplikationstransformationen für Z_n beschreiben? Zum Beispiel auf [0,1,2] ist die +0 | x1-Transformation, [1,2,0] ist die +1-Transformation ...Z3
Chad Brewbaker
72

P = BPP?

Diego de Estrada
quelle
2
Diese Antwort sollte jetzt auch CW gemacht werden ...
Shane
2
und verwandte Fragen wie NP = MA = AM?
Robin Kothari
1
Siehe die eng verwandte Frage cstheory.stackexchange.com/questions/64/…
András Salamon
66

Gibt es eine Schwenkregel für den Simplex-Algorithmus, die die Laufzeit des ungünstigsten Polynoms ergibt? Gibt es allgemein einen stark polynomialen Algorithmus für die lineare Programmierung?

Jɛ ɛ E
quelle
11
Ich füge dieser Frage hinzu: Würde das Nichtvorhandensein von stark polynomialen LP zu Ergebnissen einer Klassentrennung führen?
Anand Kulkarni
,,, und die Hirsch-Vermutung ...
Sariel Har-Peled
7
Im Jahr 2011 zeigte Oliver Friedmann exponentielle Untergrenzen für viele Pivot-Regeln (er behauptet tatsächlich "im Wesentlichen alle natürlichen" Pivot-Regeln, einschließlich Random Facet und Random Edge). Diese Grenzen gelten für das Lösen eines linearen Programms, das aus Paritätsspielen für 2 Spieler abgeleitet wurde. Friedmanns Dissertation edoc.ub.uni-muenchen.de/13294 beschäftigt sich eingehend mit der Geschichte (unter anderem mit verschiedenen Formen der Hirsch-Vermutung und dem Gegenbeispiel 2010 zur starken Form von Francisco Santos).
András Salamon
63

Die Exponential-Zeit-Hypothese (ETH) besagt , dass das Lösen von SAT eine Exponentialzeit von 2 Ω (n) erfordert . Die ETH impliziert viele Dinge, zum Beispiel, dass SAT nicht in P ist, also impliziert die ETH P ≠ NP. Siehe Impagliazzo, Paturi, Zane, welche Probleme haben eine stark exponentielle Komplexität? JCSS 63, 512–530, 2001.

Es wird allgemein angenommen, dass die ETH schwer zu beweisen ist, da dies viele andere Trennungen von Komplexitätsklassen impliziert.

András Salamon
quelle
4
Im Ernst, ich würde die ETH zu diesem Zeitpunkt nicht als ein großes offenes Problem bezeichnen, weil es P it NP impliziert und daher mindestens ebenso schwierig zu beweisen ist.
Holger
17
Nein? Meiner Meinung nach impliziert Ihr Argument, dass die ETH ein noch größeres offenes Problem darstellt als PvsNP.
Jeffs
Können Sie erklären, warum nicht die ETH impliziert? PNP
Emil
13
Wenn , dann ist , aber ETH ist falsch. P N PNP=PTIME(nlogn)PNP
Jeffs
3
Ach ok Aber meinst du DTIME ( )? nlogn
Emil
59

Immerman und Vardi zeigen, dass die Festkomma-Logik PTIME in der Klasse der geordneten Strukturen erfasst . Eines der größten offenen Probleme in der deskriptiven Komplexitätstheorie ist, ob die Abhängigkeit von der Ordnung beseitigt werden kann:

Gibt es eine Logik, die PTIME erfasst?

Einfach ausgedrückt ist eine PTIME-Erfassungslogik eine Programmiersprache für Diagrammprobleme, die direkt an der Diagrammstruktur arbeitet und keinen Zugriff auf die Codierung der Scheitelpunkte und Kanten hat, sodass Folgendes gilt:

  1. Jedes syntaktisch korrekte Programm modelliert ein polynomiell berechenbares Graphproblem und
  2. Jedes polynomiell berechenbare Graphproblem kann durch ein syntaktisch korrektes Programm modelliert werden.

Wenn es keine Logik gibt, die PTIME erfasst, wird da NP vorhanden ist, durch eine Logik zweiter Ordnung erfasst. Eine logische Erfassung von PTIME würde einen möglichen Angriff auf P vs NP darstellen.PNP

In Liptons Blog finden Sie eine informelle Diskussion, und in M. Grohe: Die Suche nach einer logischen Erfassung von PTIME (LICS 2008) finden Sie eine technischere Übersicht.

Holger
quelle
3
Immerman-Vardi zeigt, dass FO (LFP) die Logik von <i> geordneten </ i> Strukturen erfasst. Ich nehme an, dies ist eine Frage zur Erfassung von PTIME auf beliebigen endlichen Modellen. Wenn ich Sie richtig verstehe, ist diese Frage nicht eine Übersetzung der Frage, ob P! = NP ist? Es ist möglicherweise sinnvoller, eines oder mehrere der offenen Probleme in der Umfrage zu erfragen, auf die Sie verweisen. Entschuldigung, wenn ich hier keine Ahnung habe.
Aaron Sterling
5
Danke, ich habe die Antwort bearbeitet, um Immerman-Vardi zur Klarstellung zu erwähnen. Nein, es ist nicht bekannt, dass dieses offene Problem P vs NP entspricht. Die offenen Probleme in der Umfrage sind Spezialfälle des großen offenen Problems und in diesem Thread nicht angebracht. Diese Referenz ist möglicherweise auch hilfreich: rjlipton.wordpress.com/2010/04/05/…
Holger
55

Ist die Vermutung der einzigartigen Spiele wahr?
Und: Angesichts der Tatsache, dass es für Unique Games subexponentielle Zeitnäherungsalgorithmen gibt , wo liegt das Problem letztendlich in Bezug auf die Komplexitätslandschaft?

Anand Kulkarni
quelle
Wäre es nicht genauer zu sagen, dass wenn die UGC nicht wahr ist (dh einzigartige Spiele sind nicht NP-hart, nur härter als P), wo würde UGC in die Landschaft passen?
András Salamon
Hoppla. Ja, ich sollte das umformulieren. Meine Absicht war es, die offensichtliche Diskrepanz hervorzuheben, die sich aus einzigartigen Spielen mit einem nicht-trivialen Approximationsalgorithmus in subexponentieller (aber nicht ganz polynomieller) Zeit ergibt. Mehr von: Was bedeutet dies, wenn die subexponentielle Laufzeit für einzigartige Spiele optimal ist?
Daniel Apon
2
Rückblickend dachte ich, ich sollte einen Zeiger auf diesen Vordruck einfügen . Meiner Meinung nach ist es eine ebenso große Entwicklung wie das Papier, das ich in der Antwort verlinkt habe.
Daniel Apon
1
Es ist erwähnenswert, dass es keine bekannten Hard Instances von UCG gibt. Der derzeit beste Ansatz funktioniert in jedem getesteten Fall effizient. Wir können einfach nicht beweisen, dass wir die pathologischsten Beispiele gefunden haben.
Stella Biderman
55

Permanent versus Determinante

Die Frage zwischen permanent und determinant ist aus zwei Gründen interessant. Erstens zählt die bleibende Zahl einer Matrix die Anzahl der perfekten Übereinstimmungen in einem zweigeteilten Graphen. Daher ist die bleibende Zahl einer solchen Matrix # P-Complete. Gleichzeitig ist die Definition der bleibenden Karte der der Determinante sehr ähnlich und unterscheidet sich letztendlich nur durch einen einfachen Vorzeichenwechsel. Determinantenberechnungen finden sich bekanntermaßen in P. Das Studium des Unterschieds zwischen der bleibenden und der determinierenden Zahl und die Anzahl der erforderlichen Determinantenberechnungen zur Berechnung der bleibenden Zahl sprechen für P im Vergleich zu #P.

Kaveh
quelle
5
Für mich ist dies kein "großes offenes Problem", da die eigentliche komplexitätstheoretische Frage (haben sie unterschiedliche Komplexitäten) von P = NP (da #P eine Obermenge von NP ist) subsumiert und mit dieser Frage beiseite gelegt wird Es gibt hier kein konkretes Problem.
David Eppstein
Dem stimme ich tatsächlich zu.
Ross Snider
10
@DavidEppstein: Per v. Det ist näher an GapP v GapL, einem Zählanalog von NP v NL. Es ist möglich, dass und damit . Außerdem ist per v det viel älter als P v NP und geht im Wesentlichen auf [Polya 1913] zurück, in dem er zeigt, dass man keine Zeichen an eine Matrix anbringen kann, um deren bleibende in ihre Determinante zu ändern (außer 2x2). Valiant führte eine Variante zu diesen Fragen ein (die zulässt, dass die Größe von det größer als n ist), da sie für die Komplexität von Bedeutung ist, aber auch die Arbeiten vor Valiant geben die Motivation "weil die bleibende Karte so schwer zu berechnen ist ..." (z. B. Gibson 1971)G a p P G a p LNLP=NPGapPGapL
Joshua Grochow
Was sind die neuesten Algorithmen zur Berechnung der Permanenz einer 0-1-Matrix? dh die Anzahl der zulässigen Permutationsmatrizen, die Sie aus einer Teilmenge der Einsen generieren können.
Chad Brewbaker
@ChadBrewbaker: siehe Mark Jerrum, Alistair Sinclair, Eric Vigoda, "Ein Polynomial-Time Approximation-Algorithmus für die Permanenz einer Matrix mit nicht negativen Einträgen", Journal of the ACM 51/4 (2004), 671, citeseerx.ist. psu.edu/viewdoc/summary?doi=10.1.1.141.116
Zsbán Ambrus
47

Können wir die FFT in weniger als Zeit berechnen ?O(nlogn)

Aus dem gleichen (sehr) allgemeinen Grund gibt es viele Fragen zur Verbesserung der Laufzeit vieler klassischer Probleme oder Algorithmen: Können All-Pair-Shortest-Paths (APSP) in Zeit?O(n3ϵ)

Bearbeiten: APSP wird rechtzeitig ausgeführt ", wobei Hinzufügungen und Vergleiche von Realkosten Stückkosten sind (alle anderen Vorgänge sind jedoch typisch) logarithmische Kosten) ": http://arxiv.org/pdf/1312.6680v2.pdf(n32Ω(logn)1/2)

Alex Andoni
quelle
3
Eine interessante Entwicklung der FFT: "* Ein O (k log n) -Zeitalgorithmus für den Fall, dass das Eingangssignal höchstens k Fourier-Koeffizienten ungleich Null hat, und * Ein O (k log n log (n / k)) Algorithmus für allgemeine Eingangssignale. " Quelle: arxiv.org/abs/1201.2501v1
Shadok
45

Ein linearer zeitdeterministischer Algorithmus für das Minimum-Spanning-Tree- Problem.

Suresh Venkat
quelle
44

NP gegen Co-NP

Die Frage NP versus co-NP ist interessant, weil NP ≠ co-NP P ≠ NP impliziert (da P unter Komplement abgeschlossen ist). Es bezieht sich auch auf "Dualität": Trennung zwischen Finden / Verifizieren von Beispielen und Finden / Verifizieren von Gegenbeispielen. Der Beweis, dass eine Frage sowohl in NP als auch in Co-NP vorliegt, ist unser erster guter Beweis dafür, dass ein Problem, das außerhalb von P zu liegen scheint, wahrscheinlich auch nicht NP-vollständig ist.

Ross Snider
quelle
7
Dies hängt auch mit der Komplexität der Aussagen zusammen. Es gibt ein Polynomsatzbeweissystem, wenn gleich . NPcoNP
Kaveh
41

Gibt es Probleme, die von Parallelrechnern nicht effizient gelöst werden können?

Es ist nicht bekannt, dass Probleme, die P-vollständig sind, parallelisierbar sind. Zu den P-vollständigen Problemen gehören Horn-SAT und lineare Programmierung. Der Beweis, dass dies der Fall ist, erfordert jedoch die Trennung des Begriffs parallelisierbarer Probleme (wie NC oder LOGCFL) von P.

Computerprozessorkonstruktionen erhöhen die Anzahl der Verarbeitungseinheiten in der Hoffnung, dass dies zu einer verbesserten Leistung führt. Wenn grundlegende Algorithmen wie die lineare Programmierung von Natur aus nicht parallelisierbar sind, ergeben sich erhebliche Konsequenzen.

András Salamon
quelle
16
Ich bin mir ziemlich sicher, dass LP-Algorithmen nach heutigem Stand nicht parallelisierbar sind. Ich glaube, sie passen in Mulmuleys RAM-without-Bit-Operations-Modell. In dx.doi.org/10.1137/S0097539794282930 K. Mulmuley. Untere Schranken in einem Parallelmodell ohne Bitoperationen. SIAM J. Comput. 28 (4), 1460-1509 (1999) zeigt er, dass in diesem Modell ist, was zeigt, dass viele natürliche (normalerweise numerische) Algorithmen für vollständige Probleme nicht parallelisierbar sind. Dies beantwortet die Frage im Booleschen Fall nicht, aber für eine große Klasse natürlicher Algorithmen. PNCP
Joshua Grochow
41

Haben alle Aussagen-Tautologien Frege-Beweise in Polynomgröße?

Das wohl größte offene Problem der Beweiskomplexität ist die Demonstration der unteren Schranken der Superpolynomgröße für Aussagenbeweise (auch Frege-Beweise genannt).

Inoffiziell ist ein Frege-Beweissystem nur ein Standardsatzbeweissystem zum Beweisen von Satztautologien (man lernt in einem grundlegenden Logikkurs) mit Axiomen und Abzugsregeln, in denen Beweislinien als Formeln geschrieben werden. Die Größe eines Frege-Proofs ist die Anzahl der Symbole, die zum Aufschreiben des Proofs erforderlich sind.

Das Problem fragt dann, ob es eine Familie von aussagekräftigen tautologischen Formeln gibt, für die es kein Polynom so dass die minimale Frege-Beweisgröße von höchstens für alle (wobei die Größe der Formel ).(Fn)n=1pFnp(|Fn|)n=1,2,|Fn|Fn


Formale Definition eines Frege-Proof-Systems

Definition (Frege-Regel) Eine Frege-Regel ist eine Folge von Satzformeln , für , geschrieben als . Im Fall wird die Frege-Regel als Axiomschema bezeichnet . Eine Formel wird durch die Regel von wenn alle Substitutionsinstanzen von für eine Zuordnung zu den Variablen sind (d. es gibt formeln A0(x¯),,Ak(x¯)k0A1(x¯),,Ak(x¯)A0(x¯)k=0F0F1,,FkF0,,FkA1,,Akx¯B1,,Bn so dass für alle . Die Frege-Regel gilt als gültig, wenn eine Zuweisung die Formeln auf der oberen Seite und die Formel auf der unteren Seite erfüllt .Fi=Ai(B1/x1,,Bn/xn),i=0,,kA1,,AkA0

Definition (Frege-Beweis) Bei einem Satz von Frege-Regeln ist ein Frege-Beweis eine Folge von Formeln, so dass jede Proof-Linie entweder ein Axiom ist oder von einer der gegebenen Frege-Regeln aus vorherigen Proof-Linien abgeleitet wurde. Wenn die Sequenz mit der Formel endet , wird der Beweis als Beweis von . Die Größe eines Frege-Proofs ist die Gesamtgröße aller Formeln im Proof.AA

Ein Beweissystem gilt als implizit vollständig, wenn für alle Mengen von Formeln , wenn semantisch impliziert , ein Beweis für Verwendung von (möglicherweise) Axiomen aus . Ein Beweissystem gilt als solide, wenn es nur Beweise für Tautologien zulässt (wenn keine Hilfsaxiome verwendet werden, wie im obigen ).TTFFTT

Definition (Frege Proof - System) eine Aussagensprache und eine endliche Menge Gegeben von Ton Frege Regeln, wir sagen , dass ist ein Frege sicheres System , wenn implicationally abgeschlossen ist.PPP

Beachten Sie, dass ein Frege-Proof immer korrekt ist, da davon ausgegangen wird, dass die Frege-Regeln korrekt sind. Wir müssen nicht mit einem bestimmten Frege-Proof-System arbeiten, da ein grundlegendes Ergebnis der Beweiskomplexität besagt, dass alle zwei Frege-Proof-Systeme, auch über verschiedene Sprachen hinweg, polynomiell äquivalent sind [Reckhow, Doktorarbeit, University of Toronto, 1976].


Die Festlegung von Untergrenzen für Frege-Beweise könnte als ein Schritt zum Nachweis von , da in diesem Fall kein (einschließlich Frege) für alle Tautologien polynomiale haben kann.NPcoNP

Iddo Tzameret
quelle
38

Können wir den Editierabstand zwischen zwei Folgen der Länge in subquadratischer Zeit berechnen , dh in der Zeit für einige ?nO(n2ϵ)ϵ>0

Piotr
quelle
8
Haben Sie Referenzen dafür? Ich dachte tatsächlich, dass dieser Satz trivial falsch ist, obwohl ich mir keinen Beweis aus der Luft denken kann. (Obwohl mir bekannt ist, dass die Laufzeit von der Anzahl der Fehler abhängig gemacht werden kann.)
Konrad Rudolph
5
Update (STOC 2015): Backurs und Indyk geben Hinweise darauf, dass keine besser als quadratische Zeit möglich ist. Siehe rjlipton.wordpress.com/2015/06/01/puzzling-evidence .
Neal Young
38

Gibt es wirklich subquadratische Zeitalgorithmen (dh Zeit für eine Konstante ) für 3SUM-schwierige Probleme ?O(n2δ)δ>0

2014 haben Grønlund und Pettie einen deterministischen Algorithmus für 3SUM selbst beschrieben, der in der Zeit abläuft . Obwohl dies ein Hauptergebnis ist, ist die Verbesserung gegenüber nur (sub) logarithmisch. Darüber hinaus sind für die meisten anderen 3SUM-harten Probleme keine ähnlichen subquadratischen Algorithmen bekannt.O ( n 2 )O(n2/(logn/loglogn)2/3)O(n2)

Aryabhata
quelle
9
Gute Frage. Die Existenz von subquadratischen Algorithmen für das 3SUM-Problem ist jedoch selbst für randomisierte Algorithmen weit offen . Natürlich wäre der deterministische Algorithmus noch schöner gewesen.
Piotr
3
Im Quantenfall sind für 3SUM passende n log (n) -Unter- und -Obergrenzen bekannt: Andrej Dubrovsky, Oksana Scegulnaja-Dubrovska Verbesserte Quantenuntergrenzen für das 3-Summen-Problem. Proceedings of Baltic DB & IS 2004, vol. 2, Riga, Lettland, S. 40-45.
Martin Schwarz
1
Ich hatte den Eindruck, dass wir keine Untergrenze für ein Problem in NP haben.
Sariel Har-Peled
1
Ich hatte den eindeutigen Eindruck, dass, wenn Sie sich auf Entscheidungsprobleme beschränken (keine Ausgabeargumente), nichts bekannt ist. Aber Sie sollten wirklich eine komplexe Person fragen.
Sariel Har-Peled
3
Eine kürzlich erschienene Veröffentlichung von arXiv behauptet, diese Vermutung durch die Angabe subquadratischer Algorithmen für 3-SUM beigelegt zu haben.
Mangara
35

BQP = P?

Auch: NP in BQP enthalten?

Ich weiß, dass dies gegen die Regeln verstößt, da zwei Fragen in der Antwort enthalten sind. In Verbindung mit der Frage P gegen NP handelt es sich jedoch nicht unbedingt um unabhängige Fragen.

Joe Fitzsimons
quelle
33
  1. Isomorphismus-Vermutung. (Sind alle NP-vollständigen Probleme das "gleiche" Problem?)
  2. Kann Kryptographie auf einem NP-vollständigen Problem basieren?

  3. und etwas weiter vom Mainstream entfernt:

  4. Was ist die Größe von NP innerhalb von EXP?

(Informell ausgedrückt: Wenn Sie alle EXP-Probleme in einer Tabelle haben und eines nach dem Zufallsprinzip auswählen, wie hoch ist die Wahrscheinlichkeit, dass das von Ihnen gewählte Problem auch in NP vorliegt? Diese Frage wurde durch den Begriff der ressourcenbegrenzten Maßnahme formalisiert Es ist bekannt, dass P innerhalb von EXP den Wert Null hat, dh das Problem, das Sie von der Tabelle aufgegriffen haben, ist mit ziemlicher Sicherheit nicht in P.)

Aaron Sterling
quelle
Ist dies dasselbe wie p-Measure im Complexity Zoo? Wohin sollte ich gehen, um mehr darüber zu lesen?
András Salamon
2
P-Measure ist ein Beispiel für ein ressourcengebundenes Measure: Im Allgemeinen können Sie sich eine Maschine vorstellen, die versucht, eine Sequenz vorherzusagen, und die dafür verfügbaren Rechenressourcen liefern das ressourcengebundene Measure. Ich habe p-measure in meiner informellen Erklärung von EXP für eine Tabelle verwendet. Für die weitere Lektüre empfehle ich die Journalversion der folgenden Umfrage von Lutz (die CZ zitiert die Konferenzversion dieser Umfrage). cs.iastate.edu/~lutz/=PAPERS/qset.ps (im Postscript hoffe ich, dass das in Ordnung ist )
Aaron Sterling
Vielen Dank. Hier ist ein PDF des Papiers für diejenigen, die PS nicht lesen können: archives.cs.iastate.edu/documents/disk0/00/00/01/28/00000128-01/…
András Salamon
2
Ja zu deiner ersten Frage. P hat das Maß 0 in EXP. Wenn NP dies nicht tut, erhalten Sie sofort P! = NP. Für die zweite Frage schlage ich vor, dass Sie den letzten Absatz von Seite 28 in der Umfrage gelesen haben, auf die Andras und ich verlinkt haben. (Es ist nicht genug Platz im Kommentar, um ihn hier einzufügen, sorry.) Grundsätzlich gibt es, wenn NP den Wert Null hat, einen praktikablen Algorithmus, der die Zugehörigkeit zu einem NP-harten Problem "unangemessen" gut erraten könnte. Es ist also wahrscheinlich, dass NP innerhalb von EXP nicht Null ist.
Aaron Sterling
1
@Artem: Sie könnten hier anfangen: blog.computationalcomplexity.org/2003/03/…
Aaron Sterling
29

Wie ist die Approximierbarkeit von metrischem TSP ? Der Christofides-Algorithmus von 1975 ist ein Polynom-Zeit (3/2) -Annäherungsalgorithmus. Ist es NP-schwer, es besser zu machen?

  • Die Annäherung des metrischen TSP an einen Faktor kleiner als 220/219 ist NP-hart (Papadimitriou und Vempala, 2006 [PS] ). Meines Wissens ist dies die bekannteste Untergrenze.

  • Es gibt Hinweise darauf, dass die tatsächliche Grenze 4/3 sein könnte (Carr und Vempala, 2004 [Free version] [Good version] ).

  • Die Obergrenze für die Approximierbarkeit wurde kürzlich auf gesenkt (Mucha 2011 "13/9-Approximation für Grafik-TSP" [ PDF ])13/9

James King
quelle
1
Metric TSP vor kurzem von 3/2 getan - e wo e konstant ist (nahe 0,002)
Saeed
1
einige Diskussion über metrische TSP auf Gödels verlorenem Brief
Artem Kaznatcheev
2
@ Saeed, meintest du den Algorithmus nur für den Spezialfall von Metric TSP: für Graphic TSP? Dann wurde es von Mucha auf 13/9 verbessert. Es scheint, dass 3/2 die bekannteste Obergrenze für metrische TSP ist.
Alex Golovnev
@AlexGolovnev, Hallo Alex, Ja, aber mein Kommentar war vor dem Erscheinen der neuen Zeitung;) (Ich habe damals die Zeitung von Oveis Gharan gesehen).
Saeed
28

Geben Sie eine explizite Funktion mit exponentieller Schaltungskomplexität an.

Shannon hat 1949 bewiesen, dass eine zufällige Boolesche Funktion mit einer Wahrscheinlichkeit von fast eins eine exponentielle Schaltungskomplexität aufweist.

Die beste Untergrenze für eine explizite boolesche Funktion wir bisher haben, ist von K. Iwama, O. Lachish, H Morizumi und R. Raz.f:{0,1}n{0,1}5no(n)

Kaveh
quelle
11
Diese Art, das Problem zu benennen, nervt mich immer, weil Sie vorsichtig sein müssen, was Sie mit "explizit" meinen. Es ist einfach, eine Beschreibung einer Funktion mit exponentieller Schaltungskomplexität aufzuschreiben. Wenn "explizit" "in exponentieller Zeit oder weniger berechenbar" bedeutet, dann stimme ich zu, dass dies ein großes offenes Problem ist.
Ryan Williams
1
Ryan, du hast recht. Dies ist ein äußerst wichtiger Punkt. Es ist auch einfach, eine Beschreibung einer nicht berechenbaren Funktion aufzuschreiben. In dem von mir zitierten Aufsatz wird die Untergrenze für eine in deterministischer Polynomzeit konstruierbare Funktion bewiesen.
Marc
Gibt es eine gute Ausstellung über Shannons Arbeit?
T ....
3
Das Argument wird in den folgenden Vorlesungsunterlagen detailliert beschrieben: math.tau.ac.il/~zwick/scribe-boolean.html
Marc
Dies ist ein ausgezeichnetes Problem und erinnert mich an Shanons Ergebnis in meinem zweiten Studienjahr.
Stella Biderman
27

Was ist die Abfrage Komplexität des Testen Dreieck-Mahlgrad in dichten Graphen (dh Unterscheidungsdreiecksfreies Graphen von jenem -Far vom Seinem Dreieck frei)? Die bekannte obere Schranke ist ein Exponententurm in , während die bekannte untere Schranke in nur leicht überpolynomial ist . Dies ist eine ziemlich grundlegende Frage in der Extremalgraphentheorie / Additiven Kombinatorik, die seit fast 30 Jahren offen ist.1 /1 /ϵ1/ϵ1/ϵ

Arnab
quelle
27

NEXP von BPP trennen. Die Leute neigen dazu, BPP = P zu glauben, aber niemand kann NEXP von BPP trennen.

Bin Fu
quelle
26

Ich weiß, dass das OP nur ein Problem pro Post gestellt hat, aber die Konferenzen RTA (Rewriting Techniques and their Applications) 1 und TLCA (Typed Lambda Calculi and their Applications) führen beide Listen offener Probleme in ihren Bereichen 2 . Diese Listen sind sehr nützlich, da sie auch Hinweise auf frühere Arbeiten zur Lösung dieser Probleme enthalten.

Dominic Mulligan
quelle
1
Kein Problem. Kennt jemand andere ähnliche Listen von anderen Konferenzen? Es ist ziemlich interessant, sie zu lesen.
Dominic Mulligan
26

Derandomisierung des Polynomial Identity Testing-Problems

PP

Dieses Problem kann in randomisierter Polynomzeit gelöst werden, es ist jedoch nicht bekannt, dass es in deterministischer Polynomzeit lösbar ist.

τPττ(P)P1PZ[x]z(P)

cPZ[x]z(P)(1+τ(P))c

Bruno
quelle
25

Es gibt viele offene Probleme in Lambda-Kalkülen (typisiert und untypisiert). Weitere Informationen finden Sie in der TLCA-Liste der offenen Probleme . Es gibt auch eine schöne PDF-Version ohne Frames.

Ich mag besonders das Problem Nr. 5:

Gibt es in untypisierbare , die mit Hilfe von positiven rekursiven Typen typisierbar sind?Fω

Jacques Carette
quelle
3
Vielen Dank an Dominic Mulligan, der mich auf diese spezielle Liste von Problemen aufmerksam gemacht hat.
Jacques Carette
25

Ist das diskrete Logarithmusproblem in P?

Sei eine zyklische Gruppe der Ordnung und so dass ein Generator von . Das Problem, so zu finden, dass ist, ist als das diskrete Logarithmusproblem (DLP) bekannt. Gibt es einen (klassischen) Algorithmus zur Lösung des DLP in Worst-Case-Polynom-Zeit in der Anzahl der Bits von ?Gqg,hGgGnNgn=hq

Es gibt Variationen von DLP, von denen angenommen wird, dass sie einfacher sind, aber immer noch ungelöst sind. Das rechnerische Diffie-Hellman-Problem (CDH) fragt nach wenn und . Das entscheidende Diffie-Hellman-Problem (DDH) fragt nach der Entscheidung , ob , wenn .gabg,gagbg,ga,gb,hGgab=h

Es ist klar, dass DLP hart ist, wenn CDH hart ist, und CDH hart ist, wenn DDH hart ist, aber bis auf einige Gruppen keine umgekehrten Reduktionen bekannt sind. Die Annahme, dass DDH schwierig ist, ist der Schlüssel zur Sicherheit einiger Kryptosysteme wie ElGamal und Cramer-Shoup .

Felipe Lacerda
quelle
3
Nun, wir wissen, dass DLP in BQP enthalten ist.
Joe Fitzsimons
DLP wurde kürzlich für die Gruppe in Quasi-P gesetztG=Fpn×
Mark
24

Paritätsspiele sind Zwei-Spieler-Graphenspiele mit unendlicher Dauer, deren natürliches Entscheidungsproblem in NP und Co-NP liegt und deren natürliches Suchproblem in PPAD und PLS liegt.

http://en.wikipedia.org/wiki/Parity_game

Können Paritätsspiele in Polynomialzeit gelöst werden?

(Generell ist eine lange offene Frage in der mathematischen Programmierung, ob lineare Komplementaritätsprobleme in der P-Matrix in der Polynomzeit gelöst werden können.)

Rahul Savani
quelle
23

Der Bereich der parametrisierten Komplexität weist eine eigene Menge offener Probleme auf.

Betrachten Sie die Entscheidungsprobleme

  • Wenn ist, gibt es eine Scheitelpunktabdeckung der Größe für den Graphen ?(G,k)kG
  • wenn ist, gibt es eine befriedigende Zuordnung des Gewichts für die Formel ?(F,k)kF
  • Gegeben Gibt es eine Clique der Größe in einem Graphen ?(G,k)kG
  • usw...

In dieser Form gibt es viele, VIELE, kombinatorische Probleme. Parametrisierte Komplexität betrachten einen Algorithmus als "effizient", wenn seine Laufzeit durch wobei eine beliebige Funktion und eine von unabhängige Konstante ist . Zum Vergleich sei angemerkt, dass alle diese Probleme leicht in gelöst werden können . f c k n O ( k )f(k)ncfcknO(k)

Dieses Framework modelliert die Fälle, in denen wir nach einer kleinen kombinatorischen Struktur suchen und uns eine exponentielle Laufzeit in Bezug auf die Größe der Lösung / des Zeugen leisten können .

Ein Problem mit einem solchen Algorithmus (z. B. Vertex Cover) heißt Fixed Parameter Tractable (FPT).

Parametrisierte Komplexität ist eine ausgereifte Theorie, die sowohl starke theoretische Grundlagen aufweist als auch für praktische Anwendungen attraktiv ist. Für eine solche Theorie interessante Entscheidungsprobleme bilden eine sehr gut strukturierte Klassenhierarchie mit natürlichen Gesamtproblemen:

FPTW[1]W[2]W[i]W[i+1]W[P]

Natürlich ist es offen, ob eine solche Einbeziehung streng ist oder nicht. Beachten Sie, dass bei SAT einen subexponentiellen Algorithmus hat (dies ist nicht trivial). Die letzte Aussage verbindet die oben erwähnte parametrisierte Komplexität mit der .E T HFPT=W[1]ETH

Beachten Sie auch, dass die Untersuchung solcher Kollapses keine leere Aufgabe ist: Der Beweis, dass äquivalent ist, um zu beweisen, dass es einen Algorithmus mit festen Parametern gibt, mit dem man Klassen finden kann.kW[1]=FPTk

MassimoLauria
quelle