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

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).$n$$n=3$$n!=6$$A>B>C$$A>C>B$$A>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=4$$n!=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 ?$P$$P$$n$$\Omega(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.

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 .$P_n$$A_n$$n$$O(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.$A_n$$A_n$$n$

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

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 .$T_n$$n$$P_n$$T_n$$P_n$$T_n$$P_n$$\emptyset$

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).$A_n$$P_n$$n$

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.$T_n$${\mu(n)}$$T_{\mu(n)}$$T_n$$T_{\mu(n)}$$P_n$$A_n$$T_n$$A_n$$T_\emptyset$$\emptyset$

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

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.$C$$n$$|A_n|$$A_n$$C$$C$

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 .$P_n$

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.$P_n$$n$

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.

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 ).$f_n\colon\{0,1\}^n\rightarrow \{0,1\}$$P(n)$$f_n(x)$$x\in\{0,1\}^n$$\Theta(\frac{2^n}{n})$$f_n(x)$$\Theta(\frac{2^n}{n})$

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^{(2^n)}$ $n$