Graph isomorphism is in the low hierarchy

DOI10.1016/0022-0000(88)90010-4zbMath0666.68048WikidataQ55878546 ScholiaQ55878546MaRDI QIDQ1116696

Uwe Schoening

Publication date: 1988

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(88)90010-4

zbMATH Keywords

polynomial hierarchy; complexity classes; graph isomorphism; structural complexity; \(\gamma\)-reducibility

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68Q99: Theory of computing

Related Items

On the complexity of graph reconstruction, On computing Boolean connectives of characteristic functions, On closure properties of bounded two-sided error complexity classes, Star partitions and the graph isomorphism problem, ON HIGHER ARTHUR-MERLIN CLASSES, Computational indistinguishability between quantum states and its cryptographic application, The isomorphism problem for \(k\)-trees is complete for logspace, Complexity results in graph reconstruction, Graph isomorphism is low for PP, Probabilistic complexity classes and lowness, On the coding of ordered graphs, Boolean operations, joins, and the extended low hierarchy, Combinatorial techniques for universal hashing, Locating \(P\)/poly optimally in the extended low hierarchy, Solvable black-box group problems are low for PP, The counting complexity of group-definable languages, Tally NP sets and easy census functions., Some further development on the eigensystem approach for graph isomorphism detection, The Isomorphism Problem for k-Trees Is Complete for Logspace

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Some consequences of non-uniform conditions on uniform classes
• On small generators
• BPP and the polynomial hierarchy
• A low and a high hierarchy within NP
• Strong nondeterministic polynomial-time reducibilities
• Does co-NP have short interactive proofs ?
• Group-theoretic algorithms and graph isomorphism
• On counting problems and the polynomial-time hierarchy
• The polynomial-time hierarchy
• A note on the graph isomorphism counting problem
• Universal classes of hash functions
• Complexity of Presburger arithmetic with fixed quantifier dimension
• On Circuit-Size Complexity and the Low Hierarchy in NP
• On Approximation Algorithms for # P
• Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
• On the Structure of Polynomial Time Reducibility
• On Isomorphisms and Density of $NP$ and Other Complete Sets
• Computational Complexity of Probabilistic Turing Machines
• The knowledge complexity of interactive proof-systems