Graph isomorphism is low for PP

DOI10.1007/3-540-55210-3_200MaRDI QIDQ5096798zbMATH OpenOpenAlexFDO

Authors Johannes Köbler, Uwe Schöning, Jacobo Torán

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

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

Recommendations

• Graph isomorphism is low for PP
• On the Hardness of Graph Isomorphism
• Graph Isomorphism is in SPP
• scientific article; zbMATH DE number 1500534
• scientific article; zbMATH DE number 477971

Cites work

• A note on the graph isomorphism counting problem
• Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
• Complexity and structure
• Computational Complexity of Probabilistic Turing Machines
• Counting classes: Thresholds, parity, mods, and fewness
• Does co-NP have short interactive proofs ?
• Gap-definable counting classes
• 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 3702903 (Why is no real title available?)
• scientific article; zbMATH DE number 3723875 (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
• 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 complexity of theorem-proving procedures
• 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

(7)

• Graph isomorphism is in the low hierarchy
• Graph isomorphism is low for PP
• Gap-definable counting classes
• Realizability and uniqueness in graphs
• Graph Isomorphism is in SPP
• scientific article; zbMATH DE number 4007728 (Why is no real title available?)
• scientific article; zbMATH DE number 1500534 (Why is no real title available?)

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 Q5096798)