Graph isomorphism is low for PP
DOI10.1007/BF01200427zbMATH Open0770.68055OpenAlexW2365765272MaRDI QIDQ1210331FDOQ1210331
Uwe Schöning, Johannes Köbler, Jacobo Torán
Publication date: 16 September 1993
Published in: Computational Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01200427
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)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- The complexity of computing the permanent
- Complexity classes defined by counting quantifiers
- Group-theoretic algorithms and graph isomorphism
- Computational Complexity of Probabilistic Turing Machines
- The complexity of combinatorial problems with succinct input representation
- NP is as easy as detecting unique solutions
- Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
- Does co-NP have short interactive proofs ?
- The complexity of promise problems with applications to public-key cryptography
- The Knowledge Complexity of Interactive Proof Systems
- Isomorphism of graphs of bounded valence can be tested in polynomial time
- PP is as Hard as the Polynomial-Time Hierarchy
- The NP-completeness column: an ongoing guide
- Graph isomorphism is in the low hierarchy
- Relative complexity of checking and evaluating
- Probabilistic polynomial time is closed under parity reductions
- Counting classes: Thresholds, parity, mods, and fewness
- A note on the graph isomorphism counting problem
- A compact representation for permutation groups
- Relations among MOD-classes
- On the power of deterministic reductions to C=P
- Turing machines with few accepting computations and low sets for PP
- Subcomplete generalizations of graph isomorphism
Cited In (18)
- Reductions to graph isomorphism
- Promise problems and access to unambiguous computation
- No easy puzzles: hardness results for jigsaw puzzles
- Title not available (Why is that?)
- Complexity limitations on quantum computation
- An oracle builder's toolkit
- The robustness of LWPP and WPP, with an application to graph reconstruction
- The counting complexity of group-definable languages
- Solution-Graphs of Boolean Formulas and Isomorphism
- Title not available (Why is that?)
- On closure properties of GapP
- Representing Groups on Graphs
- Solvable black-box group problems are low for PP
- SZK proofs for black-box group problems
- Solution-Graphs of Boolean Formulas and Isomorphism1
- Count-free Weisfeiler-Leman and group isomorphism
- Graph Isomorphism is in SPP
- Title not available (Why is that?)
Recommendations
- Graph Isomorphism is in SPP 👍 👎
- Graph isomorphism is in the low hierarchy 👍 👎
- Reductions to graph isomorphism 👍 👎
- Reductions to Graph Isomorphism 👍 👎
- P3-isomorphisms for graphs 👍 👎
- Graph isomorphism is low for PP 👍 👎
- LOWER BOUNDS FOR SUBGRAPH ISOMORPHISM 👍 👎
- Title not available (Why is that?) 👍 👎
- Title not available (Why is that?) 👍 👎
- Title not available (Why is that?) 👍 👎
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)
