Graph isomorphism is low for PP
From MaRDI portal
Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
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
- 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
- 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?)
- 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 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
- The Knowledge Complexity of Interactive Proof Systems
- The NP-completeness column: an ongoing guide
- Turing machines with few accepting computations and low sets for PP
Cited in
(30)- Graph isomorphism is in the low hierarchy
- On closure properties of GapP
- Solvable black-box group problems are low for PP
- An oracle builder's toolkit
- The counting complexity of group-definable languages
- New lowness results for ZPP\(^{\text{NP}}\) and other complexity classes.
- Complexity limitations on quantum computation
- The robustness of LWPP and WPP, with an application to graph reconstruction
- No easy puzzles: hardness results for jigsaw puzzles
- Graph Isomorphism is in SPP
- Solution-Graphs of Boolean Formulas and Isomorphism
- Representing Groups on Graphs
- scientific article; zbMATH DE number 4007728 (Why is no real title available?)
- scientific article; zbMATH DE number 477971 (Why is no real title available?)
- scientific article; zbMATH DE number 1500534 (Why is no real title available?)
- On the Hardness of Graph Isomorphism
- The robustness of LWPP and WPP, with an application to graph reconstruction
- Solution-Graphs of Boolean Formulas and Isomorphism1
- Graph isomorphism is low for PP
- Promise problems and access to unambiguous computation
- On the complexity of identifying strongly regular graphs
- Count-free Weisfeiler-Leman and group isomorphism
- Complexity of identifying fitting-free groups
- On the descriptive complexity of groups without abelian normal subgroups
- On the parallel complexity of group isomorphism via Weisfeiler-Leman
- Canonizing graphs of bounded rank-width in parallel via Weisfeiler-Leman
- On the descriptive complexity of groups without abelian normal subgroups (extended abstract)
- Parallel complexity of identifying groups and quasigroups via decompositions
- SZK proofs for black-box group problems
- Reductions to graph isomorphism
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)
