On collapsing the polynomial-time hierarchy (Q1339382): Difference between revisions

@@ Property / Wikidata QID @@
+Q61687092
@@ Property / Wikidata QID: Q61687092 / rank @@
+Normal rank
@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / cites work @@
+Q4723714
@@ Property / cites work: Q4723714 / 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 @@
+Some Observations on Separating Complexity Classes
+Normal rank
@@ Property / cites work @@
+On Languages Reducible to Algorithmically Random Languages
+Normal rank
@@ Property / cites work @@
+An observation on probability versus randomness with applications to complexity classes
+Normal rank
@@ Property / cites work @@
+With probability one, a random oracle separates PSPACE from the polynomial-time hierarchy
+Normal rank
@@ Property / cites work @@
+A Theory of Program Size Formally Identical to Information Theory
+Normal rank
@@ Property / cites work @@
+Q4070738
@@ Property / cites work: Q4070738 / rank @@
+Normal rank
@@ Property / cites work @@
+The definition of random sequences
@@ Property / cites work: The definition of random sequences / rank @@
+Normal rank
@@ Property / cites work @@
+Process complexity and effective random tests
@@ Property / cites work: Process complexity and effective random tests / rank @@
+Normal rank
@@ Property / cites work @@
+Probabilistic complexity classes and lowness
@@ Property / cites work: Probabilistic complexity classes and lowness / rank @@
+Normal rank