Enthält P Sprachen, deren Existenz unabhängig von PA oder ZFC ist? (TCS Community Wiki)

Antwort: nicht bekannt.

Die gestellten Fragen sind natürlich, offen und anscheinend schwierig. die frage ist jetzt ein community wiki.

Überblick

Die Frage versucht, Sprachen der Komplexitätsklasse$P$  - zusammen mit den Entscheidungs-Turing-Maschinen (TMs), die diese Sprachen akzeptieren - in zwei komplementäre Unterklassen zu unterteilen:

• gnostische Sprachen und TMs (die validiert / verstanden werden können), versus
• kryptische Sprachen und TMs (die nicht validiert / verstanden werden können).

Definitionen: gnostische vs kryptische Nummern, TMs und Sprachen

Innerhalb der Axiom-Frameworks PA und ZFC unterscheiden wir gnostische von kryptischen Turing-Maschinen und -Sprachen wie folgt:

D0   Wir sagen , dass eine berechenbare reelle Zahl  ist Gnostischen iff es zu einer nicht-leeren Menge von TMs zugeordnet ist, wobei jeder TM in PA als eine expliziten Liste von Zahlen angegeben , umfassend gültigen Code auf einem Universal TM, so dass für jede Genauigkeit wird als Eingabe geliefert, und jedes TM wird nachweislich (in ZFC) mit einer Ausgabenummer angehalten, die nachweislich (in ZFC) erfüllt .$r$$\epsilon\gt0$$o$$r-\epsilon\lt o\lt r+\epsilon$

Bemerkung   Es ist bekannt, dass einige berechenbare Reelle nicht gnostisch sind (siehe Raphael Reitzigs Antwort auf die Frage von jkff " Gibt es Beweise für die Existenz eines nicht konstruktiven Algorithmus? "). Um die Auseinandersetzung mit diesen berechenbaren und dennoch umständlichen Zahlen zu vermeiden, wird die Einschränkung auferlegt, dass Laufzeitexponenten von TMs berechnet werden können, die in PA explizit aufgelistet sind (im Gegensatz zu TMs, die implizit in ZFC angegeben sind). Weitere Informationen finden Sie im Abschnitt Definitionsüberlegungen (unten).

Wir suchen nun nach Definitionen, die die Intuition erfassen, dass die Komplexitätsklasse eine Teilmenge von kryptischen Sprachen enthält, denen nachweislich kein (gnostischer) Laufzeitexponent mit Untergrenze zugeordnet werden kann. $P$

Die abschließende Definition ( D5 ) spezifiziert die Idee einer kanonisch kryptischen Entscheidung TM , deren Definition darauf abzielt, Reduktionen zu vermeiden, die kryptische Berechnungen (trivial) maskieren, indem sie rechnerisch überflüssige epi-Berechnungen überlagern. Die Gründe und Quellen dieser Schlüsseldefinition werden später - unter der Überschrift Definitionsaspekte  - erörtert, und die Beiträge von Kommentaren von Timothy Chow, Peter Shor, Sasho Nikolov und Luca Trevisan werden dankbar zur Kenntnis genommen.

D1   Bei einer Turing-Maschine M, die für alle eingegebenen Zeichenfolgen anhält, wird M als kryptisch bezeichnet, wenn die folgende Aussage für mindestens eine gnostische reelle Zahl weder beweisbar noch widerlegbar ist  :$r \ge 0$

Aussage: Die Laufzeit von M ist in Bezug auf die Eingabelänge${O}(n^r)$$n$

Wir sagen, dass Turing-Maschinen, die nicht kryptisch sind, gnostische TMs sind.

D2   Wir sagen, dass eine Entscheidungsmaschine M effizient ist, wenn sie einen gnostischen Laufzeitexponenten  so dass die Sprache L, die M akzeptiert, von keinem anderen TM mit einem gnostischen Laufzeitexponenten kleiner als akzeptiert wird  .$r$$r$

D3   Wir sagen, dass eine Sprache L kryptisch ist, wenn sie von (a)  mindestens einer Turing-Maschine M akzeptiert wird, die sowohl effizient als auch kryptisch ist, und außerdem (b)  keine TM, die sowohl effizient als auch gnostisch ist, L nachweislich akzeptiert.

Um D3 anders auszudrücken , eine Sprache ist kryptisch, wenn die TMs, die diese Sprache am effizientesten akzeptieren, selbst kryptisch sind.

Wir sagen, dass Sprachen, die nicht kryptisch sind, gnostische Sprachen sind.

D4   Wir sagen, dass ein kryptisches TM stark kryptisch ist, wenn die von ihm akzeptierte Sprache kryptisch ist.

D5   Wir sagen, dass ein stark kryptisches TM kanonisch kryptisch ist, wenn es effizient ist.

Um D5 anders auszudrücken , wird jede kryptische Sprache von einem Satz kanonisch kryptischer Entscheidungs-TMs akzeptiert, die die effizientesten Entscheidungs-TMs sind, die diese Sprache akzeptieren.

Die gestellten Fragen

Die folgende Vermutung C0 ist natürlich und (anscheinend) offen:

C0   Die Komplexitätsklasse P enthält mindestens eine kryptische Sprache.

Drei Fragen werden gestellt, Q1 - Q3 , von denen die erste ist:

Q1   Ist die C0- Vermutung unabhängig von PA oder ZFC?

Unter der Annahme, dass C0 wahr ist - entweder nachweislich in ZFC oder als unabhängiges Axiom, das ZFC ergänzt - sind zwei weitere Fragen naheliegend:

F2   Kann mindestens eine kryptische Sprache in P konkret dargestellt werden, dh als Wörterbuch expliziter Wörter in einem endlichen Alphabet, das alle Wörter bis zu einer bestimmten Länge enthält? Wenn ja, legen Sie ein solches Wörterbuch vor.

F3   Kann mindestens eine kanonisch kryptische Entscheidung TM konkret dargestellt werden, dh als eine Beschreibung für den Bau einer physischen Turing-Maschine, die (in polynomialer Zeit) alle Wörter des Wörterbuchs von Q2 entscheidet ? Wenn ja, konstruieren Sie eine solche Turing-Maschine und stellen Sie das kryptische Sprachwörterbuch von Q2 zur Verfügung, indem Sie damit rechnen .

Definitionsüberlegungen

Definition D0 impliziert, dass jede gnostische reelle Zahl berechenbar ist, aber es ist bekannt, dass einige berechenbare reelle Zahlen nicht gnostisch sind. Beispiele finden Sie in den Antworten auf MathOverflow von Michaël Cadilhac und Ryan Williams sowie auf TCS StackExchange von Raphael Reitzig . Die Definitionen D0 – D5 wurden allgemeiner formuliert , um Verweise auf nicht-gnostische Laufzeitexponenten auszuschließen.

Wie im TCS-Wiki " Enthält P unverständliche Sprachen? " Erläutert , stellen die Definitionen D0 – D5 sicher, dass jede kryptische Sprache von mindestens einem kanonisch kryptischen TM akzeptiert wird. (Beachten Sie auch, dass in der vorliegenden Frage das Wort "kryptisch" das weniger beschreibende Wort "unverständlich" ersetzt, das im Wiki verwendet wird).

Darüber hinaus gibt es - im Hinblick auf D3 (a) und D3 (b)  - keine rechnerisch triviale Reduktion eines kanonisch kryptischen TM auf ein gnostisches TM, das dieselbe Sprache nachweislich erkennt. Insbesondere D3 (a) und D3 (b) die behindern polylimiter Bekämpfungsstrategien , die in den Kommentaren von skizziert wurden Peter Shor und von Sasho Nikolov und unabhängig von Luca Trevisan und behindert auch die polynomial getaktet Reduktionsstrategie von Timothy Chow , alle von denen kryptische Berechnungen auf ähnliche Weise maskiert werden, indem eine rechnerisch überflüssige epi-Berechnung überlagert wird .

Im Allgemeinen werden die Definitionen von "gnostisch" und "kryptisch" absichtlich so abgestimmt, dass sie in Bezug auf mathematisch triviale Reduktionen robust sind (und es ist durchaus möglich, dass eine weitere Abstimmung dieser Definitionen wünschenswert sein kann).

Methodologische Überlegungen

Lance Fortnows Aufsatz " Der Status des P versus NP-Problems " untersucht Methoden zur Feststellung der Unabhängigkeit (oder auf andere Weise) von Vermutungen in der Komplexitätstheorie. Besonders erwünscht sind Vorschläge, wie die Methoden, die Lance überprüft, helfen könnten (oder nicht), um Q1 zu beantworten .

Es ist klar, dass viele weitere Fragen selbstverständlich sind. Die Hartmanis-Stearns-Vermutung inspiriert uns beispielsweise zu der Frage: "Gibt es kryptische Echtzeit-Multitape-Turing-Maschinen? Ist ihre Existenz (oder nicht) unabhängig von PA oder ZFC?"

Überlegungen vom Zeilberger-Typ

Für den Fall, dass Q1 mit "Ja" beantwortet wird, gibt es außerhalb von PA oder ZFC Orakel, die über die Zugehörigkeit zu entscheiden. Daher ist (derzeit) nicht bekannt, dass sich ein wesentliches Element der modernen Komplexitätstheorie in irgendeinem formalen System von befindet Logik. $P$

In dieser Hinsicht unterscheidet sich die Komplexitätstheorie von den meisten mathematischen Disziplinen, so dass die Befürchtungen, die Doron Zeilberger in seiner jüngsten " Stellungnahme 125: Jetzt, da Alan Turing 100 Jahre alt geworden ist, es Zeit ist, einen neuen Blick auf seine grundlegenden Beiträge zu werfen , das hat viel Gutes getan, aber auch viel Schaden "sind wohl begründet.

Zeilbergers Bedenken nehmen explizite Form als Kriterium Z0    (! Q1  ) && (! C0  ) an, was dem folgenden Kriterium entspricht:$\equiv$

Z0:   Zeilbergers Sensibilitätskriterium   Definitionen der Komplexitätsklasse P   heißen Zeilbergersensibel, wenn alle Sprachen in P nachweislich gnostisch sind.

Derzeit ist nicht bekannt, ob Stephen Cooks Definition der Komplexitätsklasse P   nach Zeilberger sinnvoll ist.

Motivierende Überlegungen

Die Definitionen von "gnostisch" und "kryptisch" werden mit Blick auf (eventuell) entscheidende Vermutungen wie die folgenden formuliert:

C1   Sei und N P ' sind die gnostischen Einschränkungen von P und N P resp. Dann ist P ' ≠ N P ' in PA oder ZFC entweder nachweisbar oder widerlegbar.$P'$$NP'$$P$$NP$$P' \ne NP'$

C2   (wie explizit in PA oder ZFC nachgewiesen)$P' \ne NP'$

Klarerweise C2   C1 , und umgekehrt ist es denkbar, dass ein Beweis des (Meta-) Theorems C1 Hinweise auf einen Beweis des (stärkeren) Theorems C2 liefert .$\to$ 

Die allgemeine Motivation ist die Erwartung / Intuition / Hoffnung, dass für eine gut abgestimmte Unterscheidung zwischen gnostischen und kryptischen TMs und Sprachen ein Beweis von C1 und möglicherweise sogar C2 einen vermutlich weitaus härteren und tieferen Sachverhalt beleuchten und sogar vergleichbare praktische Auswirkungen haben könnte Beweis dafür , dass . $P\ne NP$

Juris Hartmanis gehörte zu den ersten Komplexitätstheoretikern, die diese Forschungsrichtung ernsthaft verfolgten. siehe zum Beispiel Hartmanis 'Monographie Machbare Berechnungen und beweisbare Komplexitätseigenschaften (1978).

Nomenklaturüberlegungen

Aus dem Oxford English Dictionary (OED) haben wir:

• gnostisch (adj) In  Bezug auf Wissen; kognitiv; intellektuell   "Sie [die Zahlen] existieren in vitaler, gnostischer und spekulativer, aber nicht in operativer Weise."

• kryptisch (adj)  Nicht sofort verständlich; mysteriös, rätselhaft   "Anstelle von einfachen Regeln, die für die Menschheit nützlich sind, schieben sie [Philosophen] verdorbene und dunkle Sätze vor."

Anscheinend hat bisher keine mathematische Übersicht das Wort "gnostisch" in irgendeiner Weise verwendet. Es wird jedoch auf Marcus Krachts jüngsten Artikel „ Gnosis “ ( Journal of Philosophical Logic , MR2802332) verwiesen, in dem der OED-Sinn verwendet wird.

Anscheinend hat keine mathematische Übersicht das Wort "kryptisch" - in seinem technischen Sinne - in Bezug auf die Komplexitätstheorie verwendet. Es wird jedoch auf Charles H. Bennetts Artikel " Logical Depth and Physical Complexity " ( 1988, The Universal Turing Machine: A Half-Century Survey ) verwiesen , der die Passage enthält

Eine andere Art von Komplexität, die mit einem Objekt verbunden ist, wäre die Schwierigkeit, angesichts des Objekts eine plausible Hypothese zu finden, um es zu erklären. Objekte mit dieser Komplexität können als "kryptisch" bezeichnet werden : Einen plausiblen Ursprung für das Objekt zu finden, ist wie das Lösen eines Kryptogramms.

Überlegungen zur Natürlichkeit, Offenheit und Schwierigkeit

Die Natürlichkeit dieser Fragen verdeutlicht die These von Juris Hartmanis 'Monographie Machbare Berechnungen und Beweisbare Komplexitätseigenschaften (1978), dass:

"Ergebnisse über die Komplexität von Algorithmen ändern sich radikal, wenn wir nur Eigenschaften von Berechnungen betrachten, die formal bewiesen werden können."

Die Offenheit und Schwierigkeit dieser Fragen stimmen im Großen und Ganzen mit der Schlussfolgerung von Lance Fortnows Übersichtsartikel " The Status of the P Versus NP Problem " (2009) überein, dass:

"Keiner von uns versteht das P-gegen-NP-Problem wirklich, wir haben erst begonnen, die Schichten um diese immer komplexer werdende Frage zu schälen."

Wiki Anleitung

Besonders gefragt sind Definitionsanpassungen und Beweisstrategien, die sich speziell auf die Fragen Q1 – Q3 beziehen und die Hartmanis-Typ-Vermutungen C1 – C2 breit beleuchten .

Ich denke, dass die Frage, die Sie hier stellen (und die Sie in Ihrer verwandten Frage zu unverständlichen Sprachen gestellt haben), eine grundlegende Schwierigkeit hat.

Grob gesagt, scheint es, dass Sie eine Sprache suchen, so dass$L$

aber ZFC weiß nichtdass L ∈ P .$L\in P$$L\in P$

Um die Schwierigkeiten mit Ihrer Frage zu verstehen, müssen Sie meines Erachtens zunächst erkennen, dass es einen fundamentalen Unterschied zwischen intensionalen und extensionalen Definitionen einer Sprache . Im Allgemeinen wird L dadurch bestimmt, welche Wörter Mitglieder von L sind oder nicht . Das heißt, zwei Sprachen L und L ' sind genau dann und nur dann gleich, wenn sie genau dieselben Wörter wie Mitglieder enthalten. Im Gegensatz dazu beschreibt eine Intensionsdefinition von L einige Bedingungen, unter denen sich ein Wort in L befindet . Eine Turingmaschine, die L akzeptiert$L$$L$$L$$L$$L'$$L$$L$$L$oder eine Formel erster Ordnung , die genau dann gilt, wenn x ∈ L ist , kann als eine Intensionsdefinition von L betrachtet werden .$\phi(x)$$x\in L$$L$

Der Punkt ist, dass jedes , das (ausführlich) in P ist, eine Beschreibung zulässt, die äußerst einfach ist, weil P eine sogenannte "syntaktische" Komplexitätsklasse ist. Nehmen Sie einfach eine polynomisch getaktete Turing-Maschine, die in genau der gewünschten Zeit endet. Jedes „vernünftiges“ System zu tun Mathematik, wie PA oder ZFC, wird in der Lage sein zu beweisen , dass L ∈ P , wenn Sie diese einfache Beschreibung verwenden L .$L$$P$$P$$L\in P$$L$

Wenn Sie also ZFC verwirren möchten, müssen Sie sich eine (intensive) Beschreibung von einfallen lassen , die "zu kompliziert" ist, als dass ZFC erkennen könnte, dass sie der einfachen Beschreibung von L entspricht . Dies ist möglich, aber in gewissem Sinne ist es zu einfach, interessant zu sein. Alles, was Sie tun müssen, ist, etwas zu nehmen, von dem wir wissen, dass es von ZFC nicht verstanden wird (z. B. seine eigene Konsistenz) und es irgendwie mit der Definition von L zu verwechseln . Zum Beispiel ist hier eine Beschreibung einer Reihe von ganzen Zahlen:$L$$L$$L$

ist gerade und x codiert keinen Beweis dafür, dass ZFC inkonsistent ist.$x$$x$

Unter der Annahme, dass ZFC konsistent ist, definiert die obige Formel die Menge der geraden Ganzzahlen, aber ZFC weiß es nicht. Mit einem mehr bastelt Bit, können wir leicht eine Beschreibung des Satzes von geraden Zahlen bekommen , dass ZFC nicht in der Lage sein , in zu beweisen , .$P$

Das Fazit ist, dass, wenn Sie hoffen, dass der Grund, warum es schwierig ist zu beweisen, dass ist, dass es Sprachen in P gibt , die "zu kompliziert" sind, als dass wir darüber nachdenken könnten, ich denke, Sie bellen falsch Baum. Jede Sprache in extensions, P ist in P für triviale Gründe. Sie können das Wasser trüben, indem Sie mit unglaublich undurchsichtigen Beschreibungen von Sprachen in P herumspielen , aber dies ist ein allgemeiner Trick, der nichts mit P zu tun hat , weshalb ich glaube, dass er nicht viel Einsicht liefert.$P\ne NP$$P$$P$$P$$P$$P$

Q1: $\:$Nr.
Q2:$\:$ Ja, mindestens zwei Einsen im Binärformat

Lemma: $\:$ Jedes TM mit einem berechenbaren Laufzeitexponenten von mindestens 1 ist transzendental.

Beweis:
Sei A und B rekursiv untrennbare Mengen .$\:$$M_0$$\:$$M_1$$\;\;$$\langle r_0,r_1,r_2,r_3,...\rangle$$M_0$$M_1$$r_m$$\:m\in A\:$ dann ist die Aussage von D1 wahr] und [wenn $\:m\in B\:$ dann ist die Aussage von D1 falsch. $\;\;$$\langle r_0,r_1,r_2,r_3,...\rangle$$r_m$$\:$Daher ist die Turingmaschine transzendental.


Definition:
mindestens zwei-1s-in-binary ist die Menge nicht negativer Ganzzahlen, deren binäre
Darstellung mindestens zwei 1s hat.$\:$ (Ich wette, du hättest nie gedacht, ^ _ ^)

Definition:
M ist die Turing-Maschine, die die Binärdarstellung
ihrer Eingabe abtastet , akzeptiert, wenn sie mindestens zwei Einsen findet, und andernfalls ablehnt.

Offensichtlich entscheidet M mit mindestens zwei Einsen im Binärformat und hat den Laufzeit-Exponenten 1, und keine andere Turing-Maschine mit einem kleineren Laufzeit-Exponenten entscheidet ebenfalls mit mindestens zwei Einsen im Binärformat.
Trivialerweise$\: 1\leq 1 \:$$1$$\;\;$Durch das Lemma ist M effizient und transzendental.
Diese bedeuten, dass mindestens zwei Einsen in der Binärzahl auch transzendental sind.

Daher ist TPCCC ein Satz von PA (und ZFC), und
mindestens zwei Einsen im Binären sind eine konkrete transzendentale Sprache.

$x_n := 2 + \sum_{i=0}^n [1/2^i \mbox{ if $i$ encodes a proof that $\bf{ZF}$ is inconsistent, and 0 otherwise}]$$n$$x_n$$x_n$$x := 2 + \sum_{i=0}^\infty [1/2^i \mbox{ if $i$ encodes a proof that $\bf{ZF}$ is inconsistent, and 0 otherwise}]$

$x$$\bf{ZF}$

$x > 1$$M'_x$$n$$N$$s$$N$$s$$|s|^x/\log(|s|)$$x$$M_x$$M'_x$$M_x$$M_x$$\mathcal O(|s|^y)$$y\ge x$$M_x$

$x$$M_x$$\mathcal O(|s|^2)$$x = 2$$\bf{ZF}$$\bf ZF$$\bf ZF$$M_x$$\bf ZF + Con(\bf ZF)$

$\bf ZF + \not Con(\bf ZF)$$\bf P$$\bf ZF$$\mathcal O(|s|^z)$$z$$\bf ZF$

$M_x$