Graph Isomorphism is in SPP

DOI10.1016/j.ic.2006.02.002zbMath1110.68090OpenAlexW2020273705WikidataQ55889735 ScholiaQ55889735MaRDI QIDQ2495656

Piyush P. Kurur, V. Arvind

Publication date: 30 June 2006

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2006.02.002

zbMATH Keywords

lownessgraph isomorphismSPPcounting classes

Mathematics Subject Classification ID

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 (19)

Minimum Circuit Size, Graph Isomorphism, and Related Problems ⋮ Representing Groups on Graphs ⋮ The Isomorphism Problem for k-Trees Is Complete for Logspace ⋮ Complexity results in graph reconstruction ⋮ The size of SPP ⋮ On the Complexity of the Hidden Subgroup Problem ⋮ An oracle builder's toolkit ⋮ On the isomorphism of graphs having some eigenvalues of moderate multiplicity ⋮ Computational indistinguishability between quantum states and its cryptographic application ⋮ On the complexity of matroid isomorphism problem ⋮ Unnamed Item ⋮ The saga of minimum spanning trees ⋮ SZK proofs for black-box group problems ⋮ Graph isomorphism completeness for chordal bipartite graphs and strongly chordal graphs ⋮ LWPP and WPP are not uniformly gap-definable ⋮ The isomorphism problem for \(k\)-trees is complete for logspace ⋮ The Complexity of Symmetric Boolean Parity Holant Problems ⋮ Computational complexity of computing a partial solution for the graph automorphism problems ⋮ No easy puzzles: hardness results for jigsaw puzzles

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of computing the permanent
• Computing functions with parallel queries to NP
• A low and a high hierarchy within NP
• Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
• Does co-NP have short interactive proofs ?
• Group-theoretic algorithms and graph isomorphism
• Turing machines with few accepting computations and low sets for PP
• Graph isomorphism is low for PP
• A note on the graph isomorphism counting problem
• A taxonomy of complexity classes of functions
• Solvable black-box group problems are low for PP
• An oracle builder's toolkit
• PP-lowness and a simple definition of AWPP
• The complexity of promise problems with applications to public-key cryptography
• Bounded Round Interactive Proofs in Finite Groups
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Counting Complexity of Solvable Black-Box Group Problems
• EFFICIENT QUANTUM ALGORITHMS FOR SOME INSTANCES OF THE NON-ABELIAN HIDDEN SUBGROUP PROBLEM

This page was built for publication: Graph Isomorphism is in SPP