Komplexitätsklassen mit

21

Eine mögliche Motivation für das Studium von Computerkomplexitätsklassen besteht darin, die Leistungsfähigkeit verschiedener Arten von Computerressourcen (Zufälligkeit, Nichtdeterminismus, Quanteneffekte usw.) zu verstehen. Wenn wir es aus dieser Perspektive betrachten, dann scheint es, als könnten wir ein plausibles Axiom für jeden Versuch erhalten, zu charakterisieren, welche Berechnungen in einem Modell möglich sind:

  • Jede mögliche Berechnung kann immer eine andere mögliche Berechnung als Subroutine aufrufen. Mit anderen Worten, es sei angenommen, dass die Programme P,Q ausführbar sind. Wenn wir dann ein neues Programm durch Verknüpfen von P und Q aufbauen, so dass P Unterprogrammaufrufe für Q , ist dieses neue Programm ebenfalls möglich.

Übersetzt in die Sprache der Komplexitätsklassen ergibt sich für dieses Axiom folgende Anforderung:

  • Wenn eine Komplexitätsklasse ist, die erfassen soll, welche Berechnungen in einem Modell möglich sind, muss C C = C sein .CCC=C

(Hier stellt Berechnungen in C dar , die ein Orakel aus C aufrufen können ; das ist eine Orakelkomplexitätsklasse.) Nennen wir also eine Komplexitätsklasse C plausibel, wenn sie C C = C erfüllt .CCCCC CC=C

Meine Frage: Welche Komplexitätsklassen kennen wir, die plausibel sind (nach dieser Definition von plausibel)?

Zum Beispiel ist plausibel, da P P = P . Haben wir B P P B P P = B P P ? Was ist mit B Q P B Q P = B Q P ? Welche anderen Komplexitätsklassen erfüllen dieses Kriterium?PPP=PBPPBPP=BPPBQPBQP=BQP

Ich vermute, dass (oder zumindest, das wäre unsere beste Vermutung, auch wenn wir es nicht beweisen können). Gibt es eine Komplexitätsklasse, die nicht deterministische Berechnungen erfasst und die unter dieser Definition plausibel ist? Wenn wir C die kleinste Komplexitätsklasse bezeichnen lassen, so dass N P C und C CC , gibt es eine saubere Charakterisierung dieses C ?NPNPNPCNPCCCCC

DW
quelle
1
Sehen Sie dies , dies und das in Theoretischer Informatik - Sie müssen vorsichtig sein.
András Salamon
OK, @ AndrásSalamon, danke für die Warnung und die Hinweise! Können Sie mir helfen, zu ermitteln, wie ich mein Problem mit angemessener Vorsicht formulieren kann? Hast du irgendwelche Vorschläge? Oder, wenn die Antwort von der Formulierung abhängt, können Sie erklären, welche Antwort wir mit verschiedenen Formulierungen erhalten würden?
DW
Konstante ^ Konstante = Konstante.
Joshua

Antworten:

11

Hier sind einige Antworten auf einige der Fragen, aber sicherlich nicht alle:

Offenbar nach Wikipedia , haben wir , B P P B P P = B P P , P S P A C E P S P A C E = P S P A C E , L L = L , und P P = P . Siehe auch Was Komplexitätsklasse ist & xoplus; & xoplus;PP=PBPPBPP=BPPPSPACEPSPACE=PSPACELL=LPP=PPP , die beobachtetdass.PP=P

Auch wenn , dann C unter Ergänzung geschlossen. Somit ist es unwahrscheinlich , dass N P N P = N P : Dies würde bedeuten , dass N P = Co- N P , was unwahrscheinlich scheint. Es sieht aus wie die kleinste plausible Komplexitätsklasse , die enthält N P ist P H (siehe Wikipedia ).CC=CCNPNP=NPNP=co-NPNPPH

I don't know what the situation is with BQP. I don't know whether there are other interesting examples of plausible complexity classes.

D.W.
quelle
4
If NPNP=NP then the polynomial hierarchy collapses at level 1, i.e. Σ2P=NP. This is not generally believed to be the case (but this is an open problem). If NPC and CCC, then NPNPC and by induction C contains the polynomial hierarchy.
András Salamon
6

A complexity class C is called self-low precisely when CC=C. In general, "lowness" was studied a lot in the 80s and 90s -- google will uncover much for you.

Ryan Williams
quelle
2
Can you give some examples?
Ryan
There are examples among the other answers above: P, BPP, etc.
Ryan Williams
1
Right but have you been able to find any that haven't been mentioned before?
Ryan
4

This comment lists L (logspace), NC (polylog depth), P, BPP, BQP, and PSPACE as examples of self-low complexity classes.

tparker
quelle