On the power of parity polynomial time (Q5750401): Difference between revisions

@@ Property / cites work @@
+P-Printable Sets
@@ Property / cites work: P-Printable Sets / rank @@
+Normal rank
@@ Property / cites work @@
+Random oracles separate PSPACE from the polynomial-time hierarchy
+Normal rank
@@ Property / cites work @@
+Counting classes: Thresholds, parity, mods, and fewness
+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 @@
+On Isomorphisms and Density of $NP$ and Other Complete Sets
+Normal rank
@@ Property / cites work @@
+On the unique satisfiability problem
@@ Property / cites work: On the unique satisfiability problem / rank @@
+Normal rank
@@ Property / cites work @@
+With probability one, a random oracle separates PSPACE from the polynomial-time hierarchy
+Normal rank
@@ Property / cites work @@
+The Boolean Hierarchy I: Structural Properties
@@ Property / cites work: The Boolean Hierarchy I: Structural Properties / rank @@
+Normal rank
@@ Property / cites work @@
+The Boolean Hierarchy II: Applications
@@ Property / cites work: The Boolean Hierarchy II: Applications / rank @@
+Normal rank
@@ Property / cites work @@
+On the power of parity polynomial time
@@ Property / cites work: On the power of parity polynomial time / rank @@
+Normal rank
@@ Property / cites work @@
+Enumerative counting is hard
@@ Property / cites work: Enumerative counting is hard / rank @@
+Normal rank
@@ Property / cites work @@
+On the construction of parallel computers from various basis of Boolean functions
+Normal rank
@@ Property / cites work @@
+Near-Testable Sets
@@ Property / cites work: Near-Testable Sets / rank @@
+Normal rank
@@ Property / cites work @@
+Complexity Measures for Public-Key Cryptosystems
@@ Property / cites work: Complexity Measures for Public-Key Cryptosystems / rank @@
+Normal rank
@@ Property / cites work @@
+Q3779736
@@ Property / cites work: Q3779736 / rank @@
+Normal rank
@@ Property / cites work @@
+One-way functions and the nonisomorphism of NP-complete sets
+Normal rank
@@ Property / cites work @@
+Complexity classes without machines: on complete languages for UP
+Normal rank
@@ Property / cites work @@
+Nondeterministic Space is Closed under Complementation
+Normal rank
@@ Property / cites work @@
+Some remarks on witness functions for nonpolynomial and noncomplete sets in NP
+Normal rank
@@ Property / cites work @@
+On one-way functions and polynomial-time isomorphisms
+Normal rank
@@ Property / cites work @@
+The difference and truth-table hierarchies for NP
@@ Property / cites work: The difference and truth-table hierarchies for NP / rank @@
+Normal rank
@@ Property / cites work @@
+Collapsing degrees
@@ Property / cites work: Collapsing degrees / rank @@
+Normal rank
@@ Property / cites work @@
+A comparison of polynomial time reducibilities
@@ Property / cites work: A comparison of polynomial time reducibilities / rank @@
+Normal rank
@@ Property / cites work @@
+Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
+Normal rank
@@ Property / cites work @@
+On the Accepting Density Hierarchy in NP
@@ Property / cites work: On the Accepting Density Hierarchy in NP / rank @@
+Normal rank
@@ Property / cites work @@
+Q3815544
@@ Property / cites work: Q3815544 / rank @@
+Normal rank
@@ Property / cites work @@
+Two Results on Polynomial Time Truth-Table Reductions to Sparse Sets
+Normal rank
@@ Property / cites work @@
+Relative complexity of checking and evaluating
@@ Property / cites work: Relative complexity of checking and evaluating / rank @@
+Normal rank
@@ Property / cites work @@
+The complexity of computing the permanent
@@ Property / cites work: The complexity of computing the permanent / rank @@
+Normal rank
@@ Property / cites work @@
+The Complexity of Enumeration and Reliability Problems
+Normal rank
@@ Property / cites work @@
+Q3703298
@@ Property / cites work: Q3703298 / rank @@
+Normal rank
@@ Property / cites work @@
+On Certain Polynomial-Time Truth-Table Reducibilities of Complete Sets to Sparse Sets
+Normal rank