Characterizations of some complexity classes between _2P and _2P

DOI10.1007/3-540-55210-3_192zbMATH Open1494.68087OpenAlexW155701594MaRDI QIDQ5096790FDOQ5096790

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

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

Mathematics Subject Classification ID

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

Cites Work

• On truth-table reducibility to SAT
• A taxonomy of problems with fast parallel algorithms
• RelativizedNC
• Bounded Query Classes
• The difference and truth-table hierarchies for NP
• Bounded queries to SAT and the Boolean hierarchy
• On the Decomposability of $NC$ and $AC$
• Title not available (Why is that?)
• Title not available (Why is that?)
• Self-reducible sets of small density

Cited In (6)

• Title not available (Why is that?)
• On adaptive DLOGTIME and POLYLOGTIME reductions
• 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)