Gibt es natürliche Verallgemeinerungen von P gegenüber NP?

Akzeptierte Antwort

Scott Aaronsons Antwort wurde "akzeptiert" (hauptsächlich, weil es die einzige Antwort ist!)

Zusammenfassung der Antwort in einem Satz   Plausibel natürliche Verallgemeinerungen der Frage P gegen NP sind offensichtlich nicht einfacher zu lösen als P gegen NP selbst.

Ein Hindernis für eine allgemeine Antwort   Die ursprüngliche Frage ging davon aus, dass jede Komplexitätsklasse A "natürlich" mit einer nicht deterministischen Verallgemeinerung NA assoziiert ist - eine allgemeine Komplexitätsklasse A kann jedoch auf so viele Arten definiert werden, dass die Klassenabbildung N A. NA kann (anscheinend) nicht ohne weiteres eine vollständig allgemeine und offensichtlich natürliche Spezifikation erhalten.$\colon\,$$\,\to\,$

Der   Kommentar von dkuper ( unten ) enthält jedoch einen Link zu einem Vortrag von Christos Kapoutsis (LIAFA) mit dem Titel Minicomplexity , der eine Forschungsstrategie in der angegebenen Richtung beschreibt.

Eine weitere Ressource für die weitere Diskussion ist der verlorene Brief von Dick Lipton / Ken Regan Gödel und der P = NP- Aufsatz mit dem Titel Wir glauben viel, können aber wenig beweisen.

Die Frage wurde schließlich gestellt

Die Frage   Welche Eigenschaft, die von jeder Komplexitätsklasse A ⊂ P geteilt wird, die reicher als NTIME (n ln n) ist, behindert Beweise für A ⊂ NA?

Diese Frage motiviert war Scott Aaronson jüngsten Weblog Kommentare (siehe unten) und die Komplexität theoretischen Reichtum dieser Frage wurde durch Kommentare / Antworten / Essays anschließend beleuchtet Robin Kathari , Scott Aaronson , Ryan Williams , Dick Lipton und Ken Regan , und frühere TCS StackExchange- Fragen .

Beobachtungen   (1) Für alle bekannten Komplexitätsklassen A ⊂ P, die groß genug sind, um NTIME (n ln n) ⊂ A , ist das Problem A NA offen und (2) der Grund (s) für diese nahezu universelle komplexitätstheoretische Behinderung sind derzeit nicht gut verstanden.$\overset{?}{\subset}$

Wie viele Leute hatte ich die immense Schwierigkeit, P ⊂ NP zu beweisen, lange geschätzt, aber zuvor nicht gewürdigt, dass der Nachweis von A ⊂ NA ein offenes Problem für (im Wesentlichen) alle rechnerischen Komplexitätsklassen ist.

Die ursprünglich gestellte Frage

Scott Aaronson hat in seinem Weblog Shtetl Optimized die folgende TCS-Challenge veröffentlicht :

Die Shtetl-optimierte TCS-Herausforderung    Wenn Sie glauben, dass P vs. NP unentscheidbar ist, müssen Sie antworten:

Die Shtetl-optimierte TCS-Frage    Warum sagt Ihnen die Intuition, dass [ P gegen NP unentscheidbar ist ] nicht auch, dass die Fragen P gegen EXP, NL gegen PSPACE, MAEXP gegen P / Poly, TC0 gegen AC0 und NEXP gegen ACC ähnlich sind unentscheidbar?

(Falls Sie es nicht wissen, sind dies fünf Paare von Komplexitätsklassen, die sich als unterschiedlich erwiesen haben und manchmal sehr ausgefeilte Ideen verwenden.)

Antworten auf die folgende spezifische Frage werden akzeptiert:

Q1 (TCS-Literaturfrage)    Erfüllen bekannte Komplexitätsklassen A und B nachweislich A ⊂ B und NA ⊇ B, für NA die natürliche nicht deterministische Erweiterung von A?

Angenommen, die Antwort auf Q1 lautet "Ja", ist eine Erklärung erwünscht, wie es dazu kommt, dass der strikte Einschluss A ⊂ B bewiesen wurde, während der (oberflächlich ähnliche) strenge Einschluss P ⊂ NP schwer zu beweisen ist.

Wenn die Antwort auf Q1 alternativ "Nein" lautet, wird eine weitere Frage gestellt:

Q2 ( Die erweiterte Shtetl-optimierte TCS-Frage ) Sind Komplexitätsklasseneinschlüsse der allgemeinen Form A ⊂ B und NA ⊇ B - in ZFC oder einer endlichen Erweiterung von ZFC - für irgendeine "natürliche" Komplexitätsklasse nachweisbar? (wenn "ja" Beispiele konstruieren; wenn "nein" das Hindernis beweisen).

Die    Anerkennung und der Dank von PostScript gelten TCS StackExchange für die Aufrechterhaltung dieser wunderbar inspirierenden und hilfreichen mathematischen Community und Scott Aaronson für die Aufrechterhaltung seines bewundernswerten Weblogs Shtetl Optimized!

John, obwohl Ihre freundlichen Kommentare geschätzt werden, gebe ich zu, dass ich nicht verstehe, wie sich Ihre Frage auf den einfachen Punkt bezieht, den ich in der zitierten Bemerkung gemacht habe. Alles , was ich sagen wollte war , dass wir tun verschiedene Trennungen zwischen Komplexitätsklassen, wie P ≠ EXP, MA wissen _EXP ⊄P / poly, NEXP⊄ACC usw. Also, wenn Sie glauben , dass eine bestimmte Trennung, wie P ≠ NP, ist " zu tief, um in der ZF-Mengenlehre entweder bewiesen oder widerlegt zu werden "(oder was auch immer), dann scheint es mir, dass Sie die Last tragen, zu erklären, warum Sie denken, dass Trennung unabhängig von ZF sein muss, während andere Trennungen dies nicht taten Sein. Damit dieses Argument Kraft hat, sehe ich keine Notwendigkeit dafür, dass die anderen Trennungen die von Ihnen angegebene Form haben.

Aber um Ihre Frage trotzdem zu beantworten: Nun, die offensichtliche Herausforderung bei der Beantwortung besteht darin, jede Komplexitätsklasse A zu finden, für die wir beweisen können, dass A streng in NA enthalten ist, wobei NA "die natürliche nicht deterministische Erweiterung von A" ist! (Wie Robin oben ausführt, ist das Finden eines solchen A gleichbedeutend mit der Beantwortung Ihrer Frage, wie Sie sie angegeben haben.) Und die einzigen Beispiele für solche A, an die ich denken kann, sind Dinge wie ZEIT (f (n)) ( In den 1970er Jahren wurde bewiesen, dass TIME (f (n)) ≠ NTIME (f (n)) für f (n) ≤ n log * n ist, da NTIME (f (n)) eine Zeit simulieren kann, die etwas größer als f (n ist )). (Eine frühere Version dieses Beitrags behauptete, dass dies für alle bekannt seif (n). Vielen Dank an Ryan Williams für die Korrektur!) Wenn Sie also A = TIME (n) und B = NTIME (n) setzen, wird Ihre Frage tatsächlich bejaht. Ein "natürlicheres" Beispiel muss wahrscheinlich auf einen Durchbruch in der Komplexitätstheorie warten.

[Endnote: Ich möchte klarstellen, dass ich keine wichtigen Namen wie "The Shtetl Optimized this or that" gegeben habe - das waren Sidles 'Ausarbeitungen!]