scientific article; zbMATH DE number 3885883
From MaRDI portal
Publication:3220570
[For the entire collection see Zbl 0544.00005.] The author defines the two notions of positive and negative relativization of complexity classes. He surveys work done on both notions, with particular reference to relativized computation in the presence of bounds on the amount of nondeterminism, and/or the number of oracle queries available, with no other restrictions on computational resources. Some general comments are included concerning the goals of computational complexity theory.
Recommendations
Cited in
(27)- A survey of space complexity
- A uniform approach to define complexity classes
- Complexity classes as mathematical axioms. II
- Refining Nondeterminism in Relativizations of Complexity Classes
- scientific article; zbMATH DE number 4019036 (Why is no real title available?)
- scientific article; zbMATH DE number 3883611 (Why is no real title available?)
- Some Relations between Classes of Low Computational Complexity
- scientific article; zbMATH DE number 3930983 (Why is no real title available?)
- scientific article; zbMATH DE number 3985203 (Why is no real title available?)
- Relativizations of Unambiguous and Random Polynomial Time Classes
- scientific article; zbMATH DE number 4077187 (Why is no real title available?)
- scientific article; zbMATH DE number 4092777 (Why is no real title available?)
- scientific article; zbMATH DE number 4106269 (Why is no real title available?)
- scientific article; zbMATH DE number 4108743 (Why is no real title available?)
- On Tally Relativizations of $BP$-Complexity Classes
- scientific article; zbMATH DE number 1341929 (Why is no real title available?)
- scientific article; zbMATH DE number 559220 (Why is no real title available?)
- scientific article; zbMATH DE number 1008517 (Why is no real title available?)
- Capturing Relativized Complexity Classes without Order
- scientific article; zbMATH DE number 4114605 (Why is no real title available?)
- On the Relations Between Discrete and Continuous Complexity Theory
- Separating Complexity Classes Using Autoreducibility
- Affine relativization: unifying the algebrization and relativization barriers
- FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science
- Dimension Characterizations of Complexity Classes
- Logics capturing relativized complexity classes uniformly
- Kolmogorov characterizations of complexity classes
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3220570)