Randomness, relativizations, and polynomial reducibilities
- 1 January 1986
- book chapter
- Published by Springer Nature
Abstract
No abstract availableKeywords
This publication has 14 references indexed in Scilit:
- Three theorems on polynomial degrees of NP-setsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1985
- On the random oracle hypothesisPublished by Association for Computing Machinery (ACM) ,1982
- On the structure of sets in NP and other complexity classesTheoretical Computer Science, 1981
- Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1SIAM Journal on Computing, 1981
- Computational Complexity of Probabilistic Turing MachinesSIAM Journal on Computing, 1977
- Polynomial and abstract subrecursive classesJournal of Computer and System Sciences, 1976
- Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ QuestionSIAM Journal on Computing, 1975
- On the Structure of Polynomial Time ReducibilityJournal of the ACM, 1975
- Reducibility among Combinatorial ProblemsPublished by Springer Nature ,1972
- The complexity of theorem-proving proceduresPublished by Association for Computing Machinery (ACM) ,1971