Graph isomorphism is low for PP (Q5096798): Difference between revisions

@@ Property / author @@
+Johannes Köbler
@@ Property / author: Johannes Köbler / rank @@
+Normal rank
@@ Property / author @@
+Uwe Schoening
@@ Property / author: Uwe Schoening / rank @@
+Normal rank
@@ Property / author @@
+Jacobo Toran
@@ Property / author: Jacobo Toran / rank @@
+Normal rank
@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / OpenAlex ID @@
+W1577805290
@@ Property / OpenAlex ID: W1577805290 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3912033
@@ Property / cites work: Q3912033 / rank @@
+Normal rank
@@ Property / cites work @@
+Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
+Normal rank
@@ Property / cites work @@
+Counting classes: Thresholds, parity, mods, and fewness
+Normal rank
@@ Property / cites work @@
+Does co-NP have short interactive proofs ?
@@ Property / cites work: Does co-NP have short interactive proofs ? / rank @@
+Normal rank
@@ Property / cites work @@
+The complexity of theorem-proving procedures
@@ Property / cites work: The complexity of theorem-proving procedures / rank @@
+Normal rank
@@ Property / cites work @@
+The complexity of promise problems with applications to public-key cryptography
+Normal rank
@@ Property / cites work @@
+Gap-definable counting classes
@@ Property / cites work: Gap-definable counting classes / rank @@
+Normal rank
@@ Property / cites work @@
+Q4198056
@@ Property / cites work: Q4198056 / rank @@
+Normal rank
@@ Property / cites work @@
+Computational Complexity of Probabilistic Turing Machines
+Normal rank
@@ Property / cites work @@
+The knowledge complexity of interactive proof-systems
+Normal rank
@@ Property / cites work @@
+Q3253828
@@ Property / cites work: Q3253828 / rank @@
+Normal rank
@@ Property / cites work @@
+Group-theoretic algorithms and graph isomorphism
@@ Property / cites work: Group-theoretic algorithms and graph isomorphism / rank @@
+Normal rank
@@ Property / cites work @@
+Subcomplete generalizations of graph isomorphism
@@ Property / cites work: Subcomplete generalizations of graph isomorphism / rank @@
+Normal rank
@@ Property / cites work @@
+The NP-completeness column: an ongoing guide
@@ Property / cites work: The NP-completeness column: an ongoing guide / rank @@
+Normal rank
@@ Property / cites work @@
+Q4266533
@@ Property / cites work: Q4266533 / rank @@
+Normal rank
@@ Property / cites work @@
+Turing machines with few accepting computations and low sets for PP
+Normal rank
@@ Property / cites work @@
+Isomorphism of graphs of bounded valence can be tested in polynomial time
+Normal rank
@@ Property / cites work @@
+A note on the graph isomorphism counting problem
@@ Property / cites work: A note on the graph isomorphism counting problem / rank @@
+Normal rank
@@ Property / cites work @@
+Complexity and structure
@@ Property / cites work: Complexity and structure / rank @@
+Normal rank
@@ Property / cites work @@
+Graph isomorphism is in the low hierarchy
@@ Property / cites work: Graph isomorphism is in the low hierarchy / rank @@
+Normal rank
@@ Property / cites work @@
+Q3895641
@@ Property / cites work: Q3895641 / rank @@
+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 @@
+NP is as easy as detecting unique solutions
@@ Property / cites work: NP is as easy as detecting unique solutions / rank @@
+Normal rank
@@ Property / cites work @@
+The complexity of combinatorial problems with succinct input representation
+Normal rank