Gibt es eine vernünftige Vorstellung eines Näherungsalgorithmus für ein unentscheidbares Problem?

Es ist bekannt, dass bestimmte Probleme unentscheidbar sind, es ist jedoch möglich, einige Fortschritte bei ihrer Lösung zu erzielen. Zum Beispiel ist das Problem des Anhaltens nicht zu entscheiden, aber praktische Fortschritte können bei der Erstellung von Tools zum Erkennen potenzieller Endlosschleifen in Ihrem Code erzielt werden. Kachelprobleme sind oft unentscheidbar (z. B. hat diese Polyomino-Kachel ein Rechteck?), Aber auch hier ist es möglich, den Stand der Technik in diesem Bereich voranzutreiben.

Ich frage mich, ob es eine anständige theoretische Methode zur Messung des Fortschritts bei der Lösung unentscheidbarer Probleme gibt, die der theoretischen Apparatur ähnelt, die zur Messung des Fortschritts bei NP-harten Problemen entwickelt wurde. Oder scheint es so, als ob wir bei einer Ad-hoc-Einschätzung des Fortschritts stecken bleiben, wenn ich sehe, wie viel bestimmte Durchbrüche unser Verständnis für unentscheidbare Probleme fördern?

Edit : Wenn ich über diese Frage nachdenke, fällt mir ein, dass hier möglicherweise parametrisierte Komplexität relevant sein kann. Ein unentscheidbares Problem kann sich entscheiden, wenn wir einen Parameter einführen und den Wert des Parameters korrigieren. Ich bin mir jedoch nicht sicher, ob diese Beobachtung von Nutzen ist.

computability approximation-algorithms parameterized-complexity halting-problem Timothy Chow
quelle

..erinnert mich an die Theorie der abstrakten Interpretation.

Jagadish

[Zusammen mit Jagadishs Kommentar]: Sie können sich den MIT-Kurs 16.399: Abstract Interpretation ansehen . Insbesondere die Vorlesung 3 könnte für Ihren Fall nützlich sein.

MS Dousti

Die naheliegende Maßnahme, die Sie wahrscheinlich nicht mögen werden, besteht darin, einfach verschiedene Teillösungen nach ihren Domänen zu ordnen (dh die Menge der Eingaben, an denen sie arbeiten). Wofür möchten Sie das Maß verwenden?

Andrej Bauer

@Andrej: Lass mich deine Frage indirekt beantworten. Im Bereich der NP-schwierigen Probleme haben wir manchmal sehr gute Ergebnisse der Form: "Ein solches Näherungsverhältnis ist erreichbar, und eine weitere Verbesserung ist unmöglich, es sei denn, P = NP." Analoge Ergebnisse für interessante, unentscheidbare Probleme nachweisen zu können, wäre schön. Es würde uns ein Gefühl dafür geben, ob es eine intrinsische Barriere für weiteren Fortschritt gibt.

Timothy Chow

Schlagen Sie ein Konzept von "Quasialgorithmen" mit einigen Forschungen auf dem Gebiet vor

vzn

Antworten:

Im Falle des Halteproblems lautet die Antwort "noch nicht". Der Grund dafür ist, dass die standardmäßige logische Methode zur Charakterisierung der Schwierigkeit des Abschlussnachweises eines Programms (z. B. Ordnungsanalyse) dazu neigt, zu viel kombinatorische und / oder zahlentheoretische Struktur zu verlieren.

$\omega$

Dies bedeutet, dass es keine eindeutige Beziehung zwischen der beweistheoretischen Stärke der Metalogik, in der Sie die Terminierung zeigen (dies ist beispielsweise in der Umschreibungstheorie sehr wichtig), und den Funktionen gibt, für die Techniken wie die Rang-Funktions-Synthese die Terminierung zeigen können .

Für die Lambda-Rechnung haben wir eine genaue Charakterisierung der Terminierung im Hinblick auf die Typisierbarkeit: Ein Lambda-Term normalisiert sich nur dann stark, wenn er im Rahmen der Schnittmengen-Disziplin typisierbar ist. Dies bedeutet natürlich, dass eine vollständige Typinferenz für Schnittpunkttypen nicht möglich ist, aber es kann auch eine Möglichkeit zum Vergleichen von Teilinferenzalgorithmen geben.

Neel Krishnaswami
quelle

Aus einem denkwürdigen Vortrag einer Person, die einen Algorithmus implementiert hat, der ein unentscheidbares Problem löst: "Es dauert 2-3 Sekunden für alle Eingaben, die ich versucht habe".

Sariel Har-Peled
quelle

Dies beantwortet den Titel der Frage mehr als ihren Inhalt, aber Sie können auch "Annäherungen" des Halteproblems als Algorithmen betrachten, die Ihnen eine korrekte Antwort auf "fast alle" Programme geben.

Der Begriff "fast alle" Programme ist nur sinnvoll, wenn Ihr Berechnungsmodell optimal ist (im gleichen Sinne wie für Kolmogorovs Komplexität ), um Situationen zu vermeiden, in denen die Mehrheit Ihrer Programme trivial ist.

$M$ $n$ $\lt n$ $\epsilon$ $\epsilon$ $p\gt 0$

$\rho_n$ $\rho_n$ $<n$

Ted
quelle