Positive relativizations of the \(P=?\) NP problem

DOI10.1016/0022-0000(89)90014-7zbMath0678.68045OpenAlexW2078408075MaRDI QIDQ1124342

Craig A. Rich

Publication date: 1989

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

Full work available at URL: https://doi.org/10.1016/0022-0000(89)90014-7

zbMATH Keywords

relativizationreducibilitiesdeterministic polynomially time-bounded reducibilityP\(=?\) NP problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15)

Related Items

Characterizing polynomial complexity classes by reducibilities, A prioritized information fusion method for handling fuzzy decision-making problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Bounded query machines: on NP and PSPACE
• Bounded query machines: on NP( ) and NPQUERY( )
• Reductions on NP and p-selective sets
• A comparison of polynomial time reducibilities
• Quantitative Relativizations of Complexity Classes
• Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question