Graph isomorphism is in the low hierarchy
From MaRDI portal
Publication:1116696
DOI10.1016/0022-0000(88)90010-4zbMath0666.68048OpenAlexW2018099718WikidataQ55878546 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
Related Items (40)
Combinatorial techniques for universal hashing ⋮ The complexity of generating test instances ⋮ Locating \(P\)/poly optimally in the extended low hierarchy ⋮ The QAP-polytope and the graph isomorphism problem ⋮ New invariants for the graph isomorphism problem ⋮ Graphs, Simplicial Complexes and Hypergraphs: Spectral Theory and Topology ⋮ The Isomorphism Problem for k-Trees Is Complete for Logspace ⋮ Extending the characteristic polynomial for characterization of C\(_{20}\) fullerene congeners ⋮ Graph isomorphism for graph classes characterized by two forbidden induced subgraphs ⋮ Nominal Unification and Matching of Higher Order Expressions with Recursive Let ⋮ Complexity results in graph reconstruction ⋮ On the complexity of graph reconstruction ⋮ Predicting high-codimension critical transitions in dynamical systems using active learning ⋮ On computing Boolean connectives of characteristic functions ⋮ On closure properties of bounded two-sided error complexity classes ⋮ Graph isomorphism for \((H_1, H_2)\)-free graphs: an almost complete dichotomy ⋮ On the power of parity polynomial time ⋮ Solvable black-box group problems are low for PP ⋮ Getting the Lay of the Land in Discrete Space: A Survey of Metric Dimension and Its Applications ⋮ Star partitions and the graph isomorphism problem ⋮ On the isomorphism of graphs having some eigenvalues of moderate multiplicity ⋮ Detection of common subtrees with identical label distribution ⋮ The join can lower complexity ⋮ Induced minor free graphs: isomorphism and clique-width ⋮ Fixed-Parameter Tractable Canonization and Isomorphism Test for Graphs of Bounded Treewidth ⋮ Computational indistinguishability between quantum states and its cryptographic application ⋮ Unnamed Item ⋮ ON HIGHER ARTHUR-MERLIN CLASSES ⋮ On the expression complexity of equivalence and isomorphism of primitive positive formulas ⋮ Graph isomorphism is low for PP ⋮ The isomorphism problem for \(k\)-trees is complete for logspace ⋮ Unnamed Item ⋮ Graph isomorphism restricted by lists ⋮ Probabilistic complexity classes and lowness ⋮ On the coding of ordered graphs ⋮ Graph isomorphism is low for PP ⋮ Boolean operations, joins, and the extended low hierarchy ⋮ The counting complexity of group-definable languages ⋮ Some further development on the eigensystem approach for graph isomorphism detection ⋮ Tally NP sets and easy census functions.
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
This page was built for publication: Graph isomorphism is in the low hierarchy
