Welches Problem kann mit einem kurzen Programm nicht gelöst werden?

7

HINTERGRUND:

Kürzlich habe ich versucht, ein bestimmtes schwieriges Problem zu lösen, das als Eingabe ein Array von Zahlen erhält . Für war die einzige Lösung, die ich finden konnte, eine andere Behandlung für jede der Ordnungen der 3 Zahlen zu haben. Das heißt, es gibt eine Lösung für den Fall , eine andere Lösung für usw. (der Fall kann durch eine dieser beiden Lösungen gelöst werden).nn=3n!=6A>B>CA>C>BA>C=B

Wenn man an den Fall denkt, scheint es der einzige Weg zu sein, wieder alle verschiedene Ordnungen zu berücksichtigen und für jeden Fall eine andere Lösung zu entwickeln. Während die Lösung in jedem Einzelfall schnell ist, wäre das Programm selbst sehr groß. Die Laufzeitkomplexität des Problems ist also gering, aber die Komplexität der "Entwicklungszeit" oder die Komplexität der "Programmgröße" ist sehr groß.n=4n!=24

Dies veranlasste mich zu beweisen, dass mein Problem nicht durch ein kurzes Programm gelöst werden kann. Also suchte ich nach Referenzen für ähnliche Beweise.

Das erste Konzept, das ich gefunden habe, ist Kolmogorovs Komplexität ; Die Informationen, die ich zu diesem Thema gefunden habe, sind jedoch sehr allgemein gehalten und enthalten hauptsächlich Existenzergebnisse.

FRAGE:

Können Sie ein spezifisches reales Problem , so dass jedes Programm, das auf einem Eingabearray der Größe löst, eine Größe von mindestens , wobei eine zunehmende Funktion ist von ?PPnΩ(f(n))f(n)n

Da die Antwort offensichtlich von der Auswahl der Programmiersprache abhängt, nehmen wir an, dass wir in Java oder in einer Turing-Maschine programmieren - je nachdem, was für Sie bequemer ist.

Jedes unentscheidbare Problem erfüllt diese Anforderung trivial, da es überhaupt keine Lösung gibt. Also suche ich eine entscheidende Sprache.

Erel Segal-Halevi
quelle
"spezifische algorithmische" "spezifische Sequenz von algorithmischen"?
Können Sie Ihren letzten Satz bezüglich einer trivialen Antwort mit einem unentscheidbaren Problem genauer beschreiben? Ich habe eine Interpretation davon, aber ich finde es nicht überzeugend.
Babou
Müssen Sie erneut nach einer Lösung für jeden Wert von n suchen, die von Grund auf neu begründet ist? Oder gibt es eine Methode, um zum richtigen Programm zu gelangen, wenn n bekannt ist? Ich verstehe nicht, was Sie unter Komplexität der Entwicklungszeit verstehen ... hängt es von Ihrem Einfallsreichtum ab?
Babou
@babou: Wenn ein Problem unentscheidbar ist, gibt es kein Programm, das löst . Daher ist alles, was Sie über "jedes Programm, das löst " sagen, wahr, weil es nichts gibt, was dem widerspricht. Alles, was Sie über die Elemente einer leeren Menge sagen, ist trivial wahr. PPP
Erel Segal-Halevi
@babou: Ich meine, für jeden Wert von man sich eine Lösung von Grund auf überlegen . n
Erel Segal-Halevi

Antworten:

2

Ich gehe davon aus, dass Sie tatsächlich eine Aufzählung von Problemen wünschen, so dass die entsprechenden Programme eine zunehmende Sequenz in der Größe bilden. Hier ist ein Beispiel für eine solche Aufzählung. Ich beweise jedoch nur, dass die Größe über jede Grenze hinaus zunimmt, daher ist es nicht in , was Ihr Hauptpunkt zu sein schien. Ich könnte es besser versuchen, aber ich frage mich, was in dieser Antwort aus Ihrer Sicht der Frage möglicherweise nicht akzeptabel ist.O(1)

Wenn ich das richtig verstehe, möchten Sie eine Aufzählung von Problemen, die alle mit einem Algorithmus entscheidbar sind , so dass es kein einheitliches Entscheidungsverfahren für die Vereinigung dieser Probleme gibt, denn wenn es eines gäbe, wäre es ein kurzes Programm, wenn wird groß, dh es wäre .PnAnnO(1(n))

Dies bedeutet, dass die Aufzählung nicht berechenbar ist. Wenn es berechenbar wäre, wäre derjenige in der Lage, den Algorithmus aus der Kenntnis von zu berechnen , wodurch ein einheitliches Verfahren für die Vereinigung aller Probleme in der Aufzählung vorliegt.AnAnn

Daher können wir nur nach Beispielen suchen, bei denen es keine berechenbare Aufzählung von Algorithmen gibt, so dass löst .AnAnPn

Bevor wir darauf eingehen, müssen wir die Größe von a definieren

Sei eine Aufzählung von Turingmaschinen nach Gödel-Zahlen . Eine solche Gödel-Aufzählung ist berechenbar. Dann sei das folgende Problem: Wenn an allen Eingängen anhält, besteht darin, die von erkannte rekursive Menge zu erkennen , andernfalls besteht darin, die leere Menge .TnnPnTnPnTnPn

Da wir nach Untergrenzen für die Größe des Algorithmus suchen , der löst , müssen wir die Größe eines TM definieren. Für ein TM kann seine Gödel-Nummer als Größe der Maschine verwendet werden, dh als entsprechender Algorithmus. In der Tat nimmt die Anzahl der Zustände und Übergänge notwendigerweise mit , schon allein aufgrund des Taubenlochprinzips, obwohl es nicht unbedingt einheitlich ist (und es hängt sowieso von einer willkürlichen Definition der Größe ab).AnPnn

Dann notieren wir für jedes TM , das immer anhält, die kleinste Gôdel-Zahl eines TM so dass es immer anhält und dieselbe rekursive Menge wie erkennt . Daher ist das kleinste TM, das tatsächlich ein Algorithmus zum Lösen von , dh es ist . Wenn nicht anhalten darf, verwenden wir für einfach immer einen Algorithmus, der einem TM der das Set erkennt , immer das gleiche.Tnμ(n)Tμ(n)TnTμ(n)PnAnTnAnT

Jedes Problem ist entscheidbar und ist eine Entscheidungsprozedur. Die Aufzählung ist jedoch nicht berechenbar, aber wir haben gezeigt, dass sie unvermeidbar ist.PnAnAn

Es ist leicht zu zeigen, dass es bei jeder Konstanten ein so dass die Größevon größer als . Der Grund ist einfach, dass die Anzahl der Maschinen, die kleiner als sind, endlich ist, während die Anzahl der von TMs erkannten rekursiven Mengen unendlich ist.Cn|An|AnCC

Das ist also ein Beispiel für ein Problem (genauer gesagt eine Problemaufzählung), das nicht durch ein kurzes Programm gelöst werden kann, dh so, dass für jedes keine Konstante an die Länge der Lösungen gebunden ist .Pn

Wir können jedem Problem immer hinzufügen, dass es einer Lösung bedarf, um zuerst ein Array der Größe zu lesen , um die Einschränkung in der Frage zu erfüllen. Aber es hat wenig Sinn.Pnn

babou
quelle
Vielen Dank. Dies beantwortet in der Tat die Frage. Was ich wirklich suche (aber nicht weiß, wie ich richtig fragen soll), ist ein natürliches Problem, ein Problem, das im wirklichen Leben auftritt, wo die Größe des Programms mit der Größe der Eingabe zunimmt.
Erel Segal-Halevi
@ErelSegalHale Ich war mir dieses Aspekts des realen Lebens bewusst, bin mir aber nicht sicher, was ihn von einer TM-Antwort unterscheiden würde, angesichts der besonderen Eigenschaften des Problems, wie beispielsweise der nicht berechenbaren Aufzählbarkeit von Lösungen. Wenn Ihre Problemaufzählung natürlich ist, habe ich mich tatsächlich gefragt, wie Sie beweisen können, dass sie alle entscheidbar sind, es sei denn, sie wurden so konstruiert. Unentscheidbarkeit wird normalerweise (letztendlich) durch Widerspruch bewiesen, aber Entscheidbarkeit wird normalerweise konstruktiv bewiesen, was bedeutet, das Entscheidungsverfahren für alle anzugeben, was Sie nicht tun können, da sie nicht berechenbar aufzählbar sind.
Babou
"Ich bin nicht sicher, was es von einer TM-Antwort unterscheiden würde, angesichts der ... nicht berechenbaren Aufzählbarkeit von Lösungen" - Dies ist ein guter Punkt, danke.
Erel Segal-Halevi
7

Für jedes Problem können Sie eine Programmiersprache erstellen, in der ein Programm zum Codieren der Lösung für dieses Problem aus einem einzelnen Zeichen besteht. (vgl. HQ9 + ). Die Komplexität von Kolmogorov ist sprachabhängig. Die Antwort auf Ihre Frage, welche Probleme eine Explosion verursachen, hängt stark von der von Ihnen gewählten "Standardformalsprache" ab.

Es gibt jedoch einige interessante Ergebnisse. Das Codieren zufällig generierter Zeichenfolgen erfordert immer Kosten, die proportional zur Größe der Zeichenfolge sind. Das Pigeonhole-Prinzip besagt, dass es in jeder festen Sprache L immer einige Funktionen geben wird, die nicht in einem Raum ausgedrückt werden können, der kleiner ist als eine vollständige Aufzählung aller Fälle. Und Blums Größensatz sagt uns, dass es für eine Gesamtsprache immer Funktionen gibt, die Sie größer als einen willkürlich gewählten Blowup-Faktor codieren können, verglichen mit der Codierung derselben Funktion in einer vollständigen Turing-Sprache.

dmbarbour
quelle
"∃ funktioniert in jeder festen Sprache L, die nicht in einem Raum ausgedrückt werden kann, der kleiner ist als eine vollständige Aufzählung aller Fälle." Was ist in allen Fällen? Haben Sie eine Referenz im Web?
Babou
Ich meine eine vollständige Aufzählung von (Domänen-, Bereichs-) Paaren. Sie können solche Funktionen erstellen, z. B. die Zuordnung von einem festen Satz zufälliger Zeichenfolgen zu einem anderen festen Satz zufälliger Zeichenfolgen. Entschuldigung, ich habe keinen Hinweis darauf.
dmbarbour
Ich denke, Sie meinen eine Aufzählung solcher Probleme, so dass jedes so groß sein muss wie die Aufzählung der n Paare (Domäne, Bereich) (Ist das richtig?). Schade, dass Sie keine Ahnung haben, ob Sie weitere Informationen dazu finden. PnPn
Babou
6

Ein Ergebnis von Shannons Zuständen, dass es eine Folge von Funktionen gibt, so dass das Problem der Berechnung von für erfordert mindestens boolesche Operationen (dh die Schaltungskomplexität der Berechnung von beträgt mindestens ).fn:{0,1}n{0,1}P(n)fn(x)x{0,1}nΘ(2nn)fn(x)Θ(2nn)

Dieser Satz ist nicht so schwer zu erhalten, da es -ary Boolesche Funktionen gibt, während die Anzahl der Schaltungen der gegebenen Größe streng kleiner ist.2(2n) n

Zarathustra
quelle
OK, dies zeigt die Existenz eines Problems, das ein großes Programm erfordert, aber ich suche nach einem spezifischen Beweis dafür, dass ein bestimmtes (bekanntes) Problem ein großes Programm erfordert.
Erel Segal-Halevi
1
Ich wusste, dass dies keine wirklich zufriedenstellende Antwort war. Ich denke, dass die Komplexität der Schaltung der "Programmlänge" am nächsten kommt, da die Größe der Schaltung mit der Größe des Eingangs variiert, wie in Ihrem Beitrag. Untergrenzen in diesem Bereich sollten für einige spezifische Probleme bekannt sein, aber ich bin kein Experte.
Zarathustra
1
Ich würde denken, dass die Größe einer Schaltung eher der Komplexität der Programmausführung als der Größe des Programmcodes entspricht. Meine Idee ist, dass jedes Tor nur einmal benutzt wird. Es ist eine Art lineare Logik. Wenn Sie dasselbe in Software tun, in der Sie durch mehrmaliges Aufrufen von Unterprogrammen faktorisieren können, haben Sie das gleiche Ergebnis bei der Programmgröße? CC @ErelSegalHalevi
Babou