Probleme mit einer effizienten Lösung mit Ausnahme eines kleinen Teils der Eingaben

Das Stopp-Problem für Turing-Maschinen ist möglicherweise die kanonische, unentscheidbare Menge. Trotzdem beweisen wir, dass es einen Algorithmus gibt, der über fast alle Fälle entscheidet. Das Stopp-Problem gehört daher zu der wachsenden Sammlung von Personen, die das Phänomen der Komplexitätstheorie des „Schwarzen Lochs“ aufweisen, bei dem die Schwierigkeit eines nicht durchführbaren oder unentscheidbaren Problems auf einen sehr kleinen Bereich beschränkt ist, ein Schwarzes Loch, außerhalb dessen sich das Problem befindet einfach.

[Joel David Hamkins und Alexei Miasnikov, " Das Stopp-Problem ist auf einer Reihe von asymptotischen Wahrscheinlichkeit eins entscheidbar ", 2005]

Kann jemand Hinweise auf andere „Schwarze Löcher“ in der Komplexitätstheorie oder einen anderen Ort geben, an dem dieses oder verwandte Konzepte diskutiert werden?

cc.complexity-theory reference-request computability undecidability Jim Graber
quelle

Joel besucht MathOverflow regelmäßig. Sie können die Frage hier stellen, um eine Antwort von ihm zu erhalten. IIRC gab es eine Frage zum Ergebnis dort.

Kaveh

Siehe auch HeurP .

Kaveh

Vielleicht ist ein anderes Beispiel der Graphisomorphismus (ein NP-Zwischenproblem). Auf "realen Instanzen" ist es sehr einfach (trivial für zufällige Instanzen?) Und für viele Grafikklassen gibt es einen polynomiellen Zeitalgorithmus. Das "Schwarze Loch" scheint so eng zu sein, dass es nicht so einfach ist, harte Instanzen zu generieren, und nauty, eines der effizientesten Tools, um es zu lösen , wird häufig verwendet, um (harte) Instanzen zu generieren . Aber vielleicht verschwindet das "Schwarze Loch" und verlässt den armen GI in P :-D

Marzio De Biasi am

@Marzio, nicht-reale Beispiele machen normalerweise nicht einen kleinen Bruchteil aller Instanzen aus und unterscheiden sich von dem, worauf sie in der Veröffentlichung verweisen.

Kaveh

A

$A$

A^{'} = (A_{y}^{'}, A_{n}^{'})

$A' = (A'_y,A'_n)$

A_{y}^{'}

$A'_y$

A

$A$

A_{n}^{'}

$A'_n$

\bar{A}

$\bar{A}$

Probleme mit einer effizienten Lösung mit Ausnahme eines kleinen Teils der Eingaben

Antworten: