Graph isomorphism is in the low hierarchy
From MaRDI portal
Publication:1116696
DOI10.1016/0022-0000(88)90010-4zbMath0666.68048WikidataQ55878546 ScholiaQ55878546MaRDI QIDQ1116696
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
polynomial hierarchy; complexity classes; graph isomorphism; structural complexity; \(\gamma\)-reducibility
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, 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
