Graph isomorphism is low for PP
From MaRDI portal
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Recommendations
- Graph isomorphism is low for PP
- scientific article; zbMATH DE number 1500534
- Graph isomorphism is in the low hierarchy
- scientific article; zbMATH DE number 4007728
- scientific article; zbMATH DE number 619533
- Graph Isomorphism is in SPP
- Lower bounds for subgraph isomorphism
- P3-isomorphisms for graphs
- Reductions to graph isomorphism
- Reductions to Graph Isomorphism
Cites work
- scientific article; zbMATH DE number 3137403 (Why is no real title available?)
- scientific article; zbMATH DE number 3722702 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1346509 (Why is no real title available?)
- A compact representation for permutation groups
- A note on the graph isomorphism counting problem
- Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
- Complexity classes defined by counting quantifiers
- Computational Complexity of Probabilistic Turing Machines
- Counting classes: Thresholds, parity, mods, and fewness
- Does co-NP have short interactive proofs ?
- Graph isomorphism is in the low hierarchy
- Group-theoretic algorithms and graph isomorphism
- Isomorphism of graphs of bounded valence can be tested in polynomial time
- NP is as easy as detecting unique solutions
- On the power of deterministic reductions to C=P
- PP is as Hard as the Polynomial-Time Hierarchy
- Probabilistic polynomial time is closed under parity reductions
- Relations among MOD-classes
- Relative complexity of checking and evaluating
- Subcomplete generalizations of graph isomorphism
- The Knowledge Complexity of Interactive Proof Systems
- The NP-completeness column: an ongoing guide
- The complexity of combinatorial problems with succinct input representation
- The complexity of computing the permanent
- The complexity of promise problems with applications to public-key cryptography
- Turing machines with few accepting computations and low sets for PP
Cited in
(23)- SZK proofs for black-box group problems
- scientific article; zbMATH DE number 4007728 (Why is no real title available?)
- Reductions to graph isomorphism
- The counting complexity of group-definable languages
- scientific article; zbMATH DE number 477971 (Why is no real title available?)
- Complexity limitations on quantum computation
- On closure properties of GapP
- Graph isomorphism is low for PP
- Representing Groups on Graphs
- An oracle builder's toolkit
- Graph Isomorphism is in SPP
- Solvable black-box group problems are low for PP
- Count-free Weisfeiler-Leman and group isomorphism
- The robustness of LWPP and WPP, with an application to graph reconstruction
- Solution-Graphs of Boolean Formulas and Isomorphism
- No easy puzzles: hardness results for jigsaw puzzles
- New lowness results for ZPP\(^{\text{NP}}\) and other complexity classes.
- The robustness of LWPP and WPP, with an application to graph reconstruction
- On the Hardness of Graph Isomorphism
- Graph isomorphism is in the low hierarchy
- Promise problems and access to unambiguous computation
- On the complexity of identifying strongly regular graphs
- Solution-Graphs of Boolean Formulas and Isomorphism1
This page was built for publication: Graph isomorphism is low for PP
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1210331)
