Equivalence of NC^ k and AC^k-1 closures of NP and other classes

DOI10.1006/INCO.1995.1098MaRDI QIDQ1898478zbMATH OpenOpenAlexFDO

Authors Ogihara, Mitsunori

Publication date 15 September 1996

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

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

Full work available at URL https://doi.org/10.1006/inco.1995.1098

zbMATH Keywords

resource-bounded reducibility

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• On the Decomposability of NC and AC
• Generalized theorems on relationships among reducibility notions to certain complexity classes
• Reductions in circuit complexity: An isomorphism theorem and a gap theorem
• Nondeterministic NC^1 computation
• RelativizedNC

Cited in

(4)

• On the power of unambiguity in log-space
• The complexity class θp2: Recent results and applications in AI and modal logic
• Reductions to Graph Isomorphism
• Reductions to graph isomorphism

This page was built for publication: Equivalence of NC\(^ k\) and AC\(^{k-1}\) closures of NP and other classes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1898478)