Die unvernünftige Kraft der Uneinheitlichkeit

Aus der Sicht des gesunden Menschenverstandes ist es leicht zu glauben, dass das Hinzufügen von Nichtdeterminismus zu seine Potenz erheblich erweitert, dh, ist viel größer als . Schließlich erlaubt der Nichtdeterminismus einen exponentiellen Parallelismus, der zweifellos sehr mächtig erscheint. N P $\mathsf{P}$$\mathsf{NP}$$\mathsf{P}$

Wenn wir dagegen \ mathsf {P} nur um die Uneinheitlichkeit ergänzen $\mathsf{P}$und $\mathsf{P}/poly$ , ist die Intuition weniger klar (vorausgesetzt, wir schließen nichtrekursive Sprachen aus, die in $\mathsf{P}/poly$ ). Es ist zu erwarten, dass das bloße Zulassen unterschiedlicher Polynomzeitalgorithmen für unterschiedliche Eingabelängen (ohne den rekursiven Bereich zu verlassen) eine weniger leistungsfähige Erweiterung darstellt als die exponentielle Parallelität im Nichtdeterminismus.

Interessanterweise sehen wir jedoch die folgende kontraintuitive Situation , wenn wir diese Klassen mit der sehr großen Klasse vergleichen . Wir wissen , dass richtig enthält , was überraschend ist es nicht. (Schließlich erlaubt eine doppelt exponentielle Parallelität.) Andererseits können wir derzeit .N E X $\mathsf{NEXP}$$\mathsf{NEXP}$ N E X $\mathsf{NP}$$\mathsf{NEXP}$$\mathsf{NEXP}\subseteq \mathsf{P}/poly$

In diesem Sinne macht die Ungleichmäßigkeit, wenn sie zur Polynomzeit addiert wird, sie möglicherweise extrem mächtig, potenziell mächtiger als der Nichtdeterminismus. Es könnte sogar so weit gehen, eine doppelt exponentielle Parallelität zu simulieren ! Auch wenn wir glauben, dass dies nicht der Fall ist, lässt die Tatsache, dass dies derzeit nicht ausgeschlossen werden kann, dennoch darauf schließen, dass Komplexitätstheoretiker hier mit "mächtigen Kräften" zu kämpfen haben.

Wie würden Sie einem intelligenten Laien erklären, was sich hinter dieser "unvernünftigen Macht" der Uneinheitlichkeit verbirgt?

Eine kurze Antwort ist, dass dies nicht das erste ist, was ich einem Laien über die Komplexitätstheorie erklären möchte! Um die Idee der Ungleichförmigkeit überhaupt zu würdigen und sich von Nichtdeterminismus zu unterscheiden, müssen Sie mit den Definitionen von Komplexitätsklassen weiter unten im Unkraut sein, als viele Menschen bereit sind, dies zu tun.

Allerdings ist eine Perspektive, die mir bei der Erklärung von P / poly für Studenten hilfreich war, dass Ungleichmäßigkeit wirklich bedeutet, dass Sie eine unendliche Folge von immer besseren Algorithmen haben können, wenn Sie zu immer größeren Eingabelängen wechseln. In der Praxis wissen wir zum Beispiel, dass der naive Matrixmultiplikationsalgorithmus am besten für Matrizen bis zu einer Größe von etwa 100x100 funktioniert, und dann wird die Strassen-Multiplikation irgendwann besser, und die neueren Algorithmen werden nur für astronomisch große Matrizen besser würde in der Praxis niemals entstehen. Was wäre, wenn Sie die magische Fähigkeit hätten, den besten Algorithmus für jeden Bereich von n zu finden, mit dem Sie gerade gearbeitet haben?

Sicher, das wäre eine seltsame Fähigkeit, und alles in allem wahrscheinlich nicht so nützlich wie die Fähigkeit, NP-vollständige Probleme in polynomialer Zeit zu lösen. Aber genau genommen wäre es eine unvergleichliche Fähigkeit: Es ist keine, die Sie automatisch erhalten würden, selbst wenn P = NP. In der Tat können Sie erfundene Beispiele für nicht berechenbare Probleme konstruieren (z. B. hält die n- ^te Turing-Maschine bei 0 ⁿ als Eingabe an ?), Die Sie mit dieser Fähigkeit lösen können. Das ist also die Kraft der Ungleichmäßigkeit.

Um zu verstehen, warum man diese seltsame Kraft in Betracht zieht, müsste man wahrscheinlich etwas über das Streben nach dem Nachweis der unteren Schranken der Schaltung und die Tatsache sagen, dass vom Standpunkt vieler unserer Techniken der unteren Schranken die Gleichförmigkeit seltsam erscheint zusätzliche Bedingung, die wir fast nie brauchen.

Hier ist ein "glattes" Argument, das ich kürzlich zur Verteidigung der Behauptung gehört habe, dass uneinheitliche Rechenmodelle leistungsfähiger sein sollten, als wir vermuten. Einerseits wissen wir aus dem Zeithierarchiesatz, dass es Funktionen gibt, die in der Zeit berechenbar sind, die beispielsweise in der Zeit nicht berechenbar sind . Andererseits kann nach dem Satz von Lupanov jede boolesche Funktion vonO ( 2 n$O(2^{2n})$$O(2^{n})$ Eingängen durch eine Schaltung der Größe ( 1 + o ( 1 ) ) 2 n / n berechenbar. Wenn wir also behaupten, dass eine Ungleichmäßigkeit nicht viel Macht gibt, dann ist das S I Z $n$$(1+o(1))2^n/n$ sollte wie verhalten D T I M E ( f ( n ) O ( 1 ) ) , dann sollte dieser abrupt Anspruch Anschlaghaltenwenn f ( n ) wird 2 O ( n ) . Aber dieses Verhalten - zwei Komplexitätsmaße gehen Hand in Hand, bis plötzlich einer von ihnen allmächtig wird - erscheint willkürlich und etwas unnatürlich.$\mathsf{SIZE}(f(n))$$\mathsf{DTIME}(f(n)^{O(1)})$$f(n)$$2^{O(n)}$

$\mathsf{NP} \subseteq \mathsf{P/poly}$

$\mathbb{P/poly}$$\mathbb{NP}$$\mathbb{P}$$\mathbb{NP}$

$\mathbb{P/poly}$$\mathbb{NP}$

$\mathbb{NP}$

$\mathbb{NP}$$\mathbb{P/poly}$

Ein kritischer Punkt für ein gutes Verständnis, der meiner Meinung nach auch beim ersten Unterrichten des Fachs häufig vorkommt, ist die Feststellung, dass Ratschläge und "Hinweise" (dh Zertifikate) verschiedene Dinge sind und wie sie sich unterscheiden.

Für mich ist das deutlichste Beispiel für die Kraft der Ungleichmäßigkeit, dass eine entsprechend gepolsterte Version des Halteproblems bereits in P / 1 enthalten ist. Ein einziger Ratschlag reicht dann aus, um diese Sprache mit einem einfachen TM zu entscheiden, das einfach den Ratschlag zurückgibt.

Natürlich bedeutet das Auffüllen einer unentscheidbaren Sprache um einen exponentiellen Betrag, dass es nicht "moralisch" in P / Poly ist. Dies zeigt jedoch, dass man vorsichtig sein muss, wenn man Ungleichmäßigkeiten zulässt.

Ich habe den Eindruck, dass das eigentliche Problem hier die unzumutbare schwere Beweislast ist, nicht die unzumutbare Kraft der Uneinheitlichkeit. Wie die Antworten von Chazisop und András Salamon bereits belegen, sind unabdingbare Sprachen auch in sehr eingeschränkten, nicht einheitlichen Sprachen berechenbar, da auf die Beweislast vollständig verzichtet wurde.

$2^n$$n$$n$$n$$n$$2^n\exp(O(n))=\exp(n\log(2)+O(n))=\exp(O(n))$

$n$$\mathsf{NEXP}$

$\mathsf{P/poly'}\subseteq \mathsf{NP}$$n$$\mathsf{P/poly'}$$\mathsf{P}$$\mathsf{NP}\subseteq\mathsf{P/poly'}$) gilt immer noch, aber diese Aussage ist weniger interessant als das echte Karp-Lipton-Theorem.