Graph isomorphism is low for PP

DOI10.1007/BF01200427zbMath0770.68055OpenAlexW2365765272MaRDI QIDQ1210331

Uwe Schoening, Johannes Köbler, Jacobo Toran

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

zbMATH Keywords

graph isomorphism

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (16)

On closure properties of GapP ⋮ Representing Groups on Graphs ⋮ Promise problems and access to unambiguous computation ⋮ Solvable black-box group problems are low for PP ⋮ An oracle builder's toolkit ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Complexity limitations on quantum computation ⋮ SZK proofs for black-box group problems ⋮ Graph Isomorphism is in SPP ⋮ Reductions to graph isomorphism ⋮ The robustness of LWPP and WPP, with an application to graph reconstruction ⋮ Solution-Graphs of Boolean Formulas and Isomorphism ⋮ The counting complexity of group-definable languages ⋮ Solution-Graphs of Boolean Formulas and Isomorphism1 ⋮ No easy puzzles: hardness results for jigsaw puzzles

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of computing the permanent
• Probabilistic polynomial time is closed under parity reductions
• Relations among MOD-classes
• NP is as easy as detecting unique solutions
• The complexity of combinatorial problems with succinct input representation
• Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
• 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
• Turing machines with few accepting computations and low sets for PP
• Relative complexity of checking and evaluating
• A note on the graph isomorphism counting problem
• Subcomplete generalizations of graph isomorphism
• PP is as Hard as the Polynomial-Time Hierarchy
• The complexity of promise problems with applications to public-key cryptography
• A compact representation for permutation groups
• The NP-completeness column: an ongoing guide
• The Knowledge Complexity of Interactive Proof Systems
• On the power of deterministic reductions to C=P
• Computational Complexity of Probabilistic Turing Machines
• Complexity classes defined by counting quantifiers
• Counting classes: Thresholds, parity, mods, and fewness

This page was built for publication: Graph isomorphism is low for PP