With probability one, a random oracle separates PSPACE from the polynomial-time hierarchy (Q1118405): Difference between revisions

The Lebesgue measure on [0,1] carries over to a measure on the oracle space $2^{\{0,1\}^*}$ by identifying subsets of $\{0,1\}^*$ via their characteristic functions with reals. It is shown that the set of all oracles A with $PSPACE^ A\neq PH^ A$ has measure 1.

0 references

zbMATH Keywords

PSPACE

0 references

polynomial time hiararchy

0 references

random oracle

0 references

MaRDI profile type

MaRDI publication profile

0 references

cites work

$\Sigma_ 1^ 1$-formulae on finite structures

0 references

Relative to a Random Oracle<i>A</i>, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1

0 references

Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question

0 references

A second step toward the polynomial hierarchy

0 references

Q3751004

0 references

Alternation

0 references

Parity, circuits, and the polynomial-time hierarchy

0 references

Q3862379

0 references

The polynomial-time hierarchy

0 references

Identifiers

zbMATH Open document ID

0668.68052

0 references

DOI

10.1016/0022-0000(89)90033-0

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:1118405

@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / OpenAlex ID @@
+W4300757861
@@ Property / OpenAlex ID: W4300757861 / rank @@
+Normal rank
@@ Property / cites work @@
+\(\Sigma_ 1^ 1\)-formulae on finite structures
@@ Property / cites work: \(\Sigma_ 1^ 1\)-formulae on finite structures / rank @@
+Normal rank
@@ Property / cites work @@
+Relative to a Random Oracle<i>A</i>, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
+Normal rank
@@ Property / cites work @@
+Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
+Normal rank
@@ Property / cites work @@
+A second step toward the polynomial hierarchy
@@ Property / cites work: A second step toward the polynomial hierarchy / rank @@
+Normal rank
@@ Property / cites work @@
+Q3751004
@@ Property / cites work: Q3751004 / rank @@
+Normal rank
@@ Property / cites work @@
+Alternation
@@ Property / cites work: Alternation / rank @@
+Normal rank
@@ Property / cites work @@
+Parity, circuits, and the polynomial-time hierarchy
+Normal rank
@@ Property / cites work @@
+Q3862379
@@ Property / cites work: Q3862379 / rank @@
+Normal rank
@@ Property / cites work @@
+The polynomial-time hierarchy
@@ Property / cites work: The polynomial-time hierarchy / rank @@
+Normal rank