Graph isomorphism is low for PP

DOI10.1007/3-540-55210-3_200zbMath1494.68200OpenAlexW1577805290MaRDI QIDQ5096798

Jacobo Toran, Uwe Schoening, Johannes Köbler

Publication date: 18 August 2022

Published in: STACS 92 (Search for Journal in Brave)

Full work available at URL: http://nbn-resolving.de/urn:nbn:de:bsz:289-vts-69537

Mathematics Subject Classification ID

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)

Related Items

Realizability and uniqueness in graphs ⋮ Gap-definable counting classes

Cites Work

• The complexity of computing the permanent
• Complexity and structure
• 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
• Gap-definable counting classes
• Subcomplete generalizations of graph isomorphism
• The complexity of promise problems with applications to public-key cryptography
• The NP-completeness column: an ongoing guide
• Computational Complexity of Probabilistic Turing Machines
• The knowledge complexity of interactive proof-systems
• The complexity of theorem-proving procedures
• Counting classes: Thresholds, parity, mods, and fewness
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item