Characterizations of some complexity classes between _2P and _2P

DOI10.1007/3-540-55210-3_192MaRDI QIDQ5096790zbMATH OpenOpenAlexFDO

Authors Jorge Castro, Carlos Seara

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

Mathematics Subject Classification ID

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

Recommendations

• Complexity classes between $\Theta _k^P$ and $\Delta _k^P$
• scientific article; zbMATH DE number 4060725
• Bounded Query Classes
• scientific article; zbMATH DE number 223336
• Quantitative Relativizations of Complexity Classes

Cites work

• scientific article; zbMATH DE number 3930351 (Why is no real title available?)
• scientific article; zbMATH DE number 3988706 (Why is no real title available?)
• A taxonomy of problems with fast parallel algorithms
• Bounded Query Classes
• Bounded queries to SAT and the Boolean hierarchy
• On the Decomposability of $NC$ and $AC$
• On truth-table reducibility to SAT
• RelativizedNC
• Self-reducible sets of small density
• The difference and truth-table hierarchies for NP

Cited in

(7)

• scientific article; zbMATH DE number 2080215 (Why is no real title available?)
• On adaptive DLOGTIME and POLYLOGTIME reductions
• Kolmogorov characterizations of complexity classes
• Computing functions with parallel queries to NP
• A novel characterization of the complexity class \(\Theta_k^{\mathrm{P}}\) based on counting and comparison
• The complexity class θp2: Recent results and applications in AI and modal logic
• Choice logics and their computational properties

This page was built for publication: Characterizations of some complexity classes between \(\Theta_2^{\mathrm{P}}\) and \(\Delta_2^{\mathrm{P}}\)

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