scientific article
From MaRDI portal
Publication:3703297
zbMath0581.68043MaRDI QIDQ3703297
Publication date: 1985
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
alternationcomplexity classesnondeterministic Turing machinepolynomial time classesalternating Tuing machinesbounded truth table reducibilitylevels of the Boolean closure of NP
Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15) Recursive functions and relations, subrecursive hierarchies (03D20) Turing machines and related notions (03D10)
Related Items (33)
A downward translation in the polynomial hierarchy ⋮ A Survey on Difference Hierarchies of Regular Languages ⋮ Relating Automata-theoretic Hierarchies to Complexity-theoretic Hierarchies ⋮ Query-monotonic Turing reductions ⋮ Polynomial terse sets ⋮ More complicated questions about maxima and minima, and some closures of NP ⋮ The logarithmic alternation hierarchy collapses: \(A\Sigma _ 2^{{\mathcal L}}=A\Pi_ 2^{{\mathcal L}}\) ⋮ Unnamed Item ⋮ Nondeterministic bounded query reducibilities ⋮ On the Complexity of Master Problems ⋮ Characterizations of some complexity classes between Θ2p and Δ2p ⋮ On the complexity of automatic complexity ⋮ From \texttt{SAT} to \texttt{SAT}-\texttt{UNSAT} using P systems with dissolution rules ⋮ The difference and truth-table hierarchies for NP ⋮ From NP-completeness to DP-completeness: a membrane computing perspective ⋮ Complexity of Topological Properties of Regular ω-Languages ⋮ The Boolean hierarchy of NP-partitions ⋮ On truth-table reducibility to SAT ⋮ Why not negation by fixpoint? ⋮ Bounded queries to SAT and the Boolean hierarchy ⋮ On the Decomposition of Abstract Dialectical Frameworks and the Complexity of Naive-based Semantics ⋮ Fine hierarchies and m-reducibilities in theoretical computer science ⋮ The complexity of unions of disjoint sets ⋮ A uniform approach to define complexity classes ⋮ On boolean lowness and boolean highness ⋮ Cognitive hierarchy and voting manipulation in \(k\)-approval voting ⋮ Nondeterministic and randomized Boolean hierarchies in communication complexity ⋮ Unnamed Item ⋮ Complexity classes between $\Theta _k^P$ and $\Delta _k^P$ ⋮ On the complexity of finding the chromatic number of a recursive graph. I: The bounded case ⋮ A reducibility for the dot-depth hierarchy ⋮ Covered clauses are not propagation redundant ⋮ A note on parallel queries and the symmetric-difference hierarchy.
This page was built for publication:
