Complexity classes and sparse oracles

DOI10.1006/JCSS.1995.1030MaRDI QIDQ1894447zbMATH OpenOpenAlexFDO

Authors Daniel P. Bovet, Pilu Crescenzi, Riccardo Silvestri

Publication date 24 July 1995

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/jcss.1995.1030

zbMATH Keywords

complexity classes

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 3978383
• On sparse oracles separating feasible complexity classes
• The polynomial-time hierarchy and sparse oracles
• scientific article; zbMATH DE number 1072529
• Sparse sets and collapse of complexity classes
• Polynomial-time random oracles and separating complexity classes
• scientific article; zbMATH DE number 3992933
• scientific article; zbMATH DE number 3883613
• scientific article; zbMATH DE number 4100610

Cited in

(13)

• Separating complexity classes with tally oracles
• On balanced versus unbalanced computation trees
• A characterization of the leaf language classes
• A uniform approach to define complexity classes
• scientific article; zbMATH DE number 1072529 (Why is no real title available?)
• Helping by unambiguous computation and probabilistic computation
• Succinct circuit representations and leaf language classes are basically the same concept
• On sparse oracles separating feasible complexity classes
• Succinct representation, leaf languages, and projection reductions
• Quantum and classical complexity classes: Separations, collapses, and closure properties
• scientific article; zbMATH DE number 3978383 (Why is no real title available?)
• scientific article; zbMATH DE number 3992933 (Why is no real title available?)
• On the acceptance power of regular languages

This page was built for publication: Complexity classes and sparse oracles

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