Characterizations of some complexity classes between Θ2p and Δ2p
From MaRDI portal
Publication:5096790
DOI10.1007/3-540-55210-3_192zbMath1494.68087OpenAlexW155701594MaRDI QIDQ5096790
Publication date: 18 August 2022
Published in: STACS 92 (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/3-540-55210-3_192
Related Items (4)
The complexity class θp2: Recent results and applications in AI and modal logic ⋮ On adaptive DLOGTIME and POLYLOGTIME reductions ⋮ Computing functions with parallel queries to NP ⋮ Choice logics and their computational properties
Cites Work
- Unnamed Item
- Unnamed Item
- On truth-table reducibility to SAT
- Bounded queries to SAT and the Boolean hierarchy
- On the Decomposability of $NC$ and $AC$
- Self-reducible sets of small density
- Bounded Query Classes
- A taxonomy of problems with fast parallel algorithms
- RelativizedNC
- The difference and truth-table hierarchies for NP
This page was built for publication: Characterizations of some complexity classes between Θ2p and Δ2p