Als «oracles» getaggte Fragen

Fragen zu Orakelmaschinen in der rechnerischen Komplexitätstheorie. Orakel können als Indikator dafür dienen, dass eine Trennung zwischen Komplexitätsklassen den Rahmen bestimmter Beweisverfahren sprengt.

20
Weltraumgebundene TMs und Orakel

Im Allgemeinen zählt das Abfrageband für ein Orakel für die räumliche Komplexität eines TM. Es erscheint jedoch plausibel, nur ein beschreibbares Orakelband zuzulassen (wie es bei L-Platz-Verkleinerungen verwendet wird). Ist eine solche Konstruktion sinnvoll? Ergibt es irgendwelche besonders...

18
P mit ganzzahligem Faktorisierungsorakel

Ich habe gerade die Frage " Ist die Faktorisierung von Ganzzahlen ein NP-vollständiges Problem? " Gelesen, also habe ich mich entschlossen, einen Teil meines Rufs auszugeben :-) und eine andere Frage gestellt: mit :P ( Q ist trivial ) ≈ 1Q.QQP( Q ist trivial ) ≈ 1P(Q is trivial)≈1P(\text{Q is...

12
als Orakel

Tut NPNP∩coNP=NPNPNP∩coNP=NP\mathsf{NP^{NP \,\cap\, coNP}=NP}halten? Klar NPNP≠NPNPNP≠NP\mathsf{NP^{NP}\neq NP} , aber es scheint mir, dass NP∩coNPNP∩coNP\mathsf{NP\cap coNP} "deterministisch" ist, was mich glauben lässt, dass dies wahr ist. Gibt es einen einfachen Beweis (oder vielleicht nur per...

11
Relativierte Welt mit

Ich würde gerne wissen, ob es eine relativierte Welt gibt, in der . Ich bin auch interessiert zu wissen, ob es eine relativierte Welt gibt, in der P B ≠ N P B = P P B ist .P.EIN= N P.EIN≠ P P.EINPA=NPA≠PPA{\bf P^A}={\bf NP^A}\not = {\bf PP^A}P.B.≠ N P.B.= P P.B.PB≠NPB=PPB{\bf P^B} \not = {\bf NP^B}...

11
Sind Orakel assoziativ?

Diese Frage mag eine offensichtliche Antwort haben ... aber hier ist die Frage trotzdem. Intuitiv ist es die folgende plausible Aussage: "Eine Maschine mit einer Subroutine A, die wiederum eine Subroutine B hat, ist dieselbe wie eine Maschine mit einer Subroutine A, die Zugriff auf Subroutine B...

10
Oracle Ergebnisse auf P vs BPP

Sei ein EXP-Komplettproblem. Dann P A = N P A .EINAAP.EIN= N.P.EINPA=NPAP^A = NP^A Sei ein Orakel, das die Abfragen berücksichtigt, die M (ein TM in P) stellen wird, und wir können P B ≠ N P B erhalten .B.BBM.MMP.B.≠ N.P.B.PB≠NPBP^B \neq NP^B Frage: Haben wir ähnliche Orakelergebnisse für P gegen...

10
Ist

Ich konnte in der Literatur keine Aussage zu MAMA\mathsf{MA} und NPRPNPRP\mathsf{NP}^\mathsf{RP} ; Hinweise wären willkommen. Ich glaube, sie sind gleich: MA⊆NPRPMA⊆NPRP\mathsf{MA} \subseteq \mathsf{NP}^\mathsf{RP} : DieNPNP\mathsf{NP} Maschine errät Merlins Saite, und dasRPRP\mathsf{RP} Orakel...