Positive relativizations of the P=? NP problem

DOI10.1016/0022-0000(89)90014-7MaRDI QIDQ1124342zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• Positive Relativizations of Complexity Classes
• Publication:3030806
• scientific article; zbMATH DE number 500314
• Quantitative Relativizations of Complexity Classes
• scientific article; zbMATH DE number 4099277

Cites work

• scientific article; zbMATH DE number 3566230 (Why is no real title available?)
• scientific article; zbMATH DE number 3571502 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A comparison of polynomial time reducibilities
• Bounded query machines: on NP and PSPACE
• Bounded query machines: on NP( ) and NPQUERY( )
• Quantitative Relativizations of Complexity Classes
• Reductions on NP and p-selective sets
• Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question

Cited in

(25)

• Honest polynomial time reducibilities and the \(P=?NP\) problem
• \(\mathrm P \overset {?} {=} \mathrm{NP}\)
• Relativizations of the P = NP problem over the complex number field
• Relativized separation of EQP from \(\text{P}^{\text{NP}}\)
• A positive relativization of polynomial time versus polylog space
• On relativizations of the P =? NP question for several structures
• Characterizing polynomial complexity classes by reducibilities
• Qualitative relativizations of complexity classes
• scientific article; zbMATH DE number 139620 (Why is no real title available?)
• Relativized alternation and space-bounded computation
• The structure of relativized P and NP questions
• scientific article; zbMATH DE number 1543330 (Why is no real title available?)
• Cook reducibility is faster than Karp reducibility in NP
• On a criterion of NP-completeness
• scientific article; zbMATH DE number 2163013 (Why is no real title available?)
• scientific article; zbMATH DE number 4019036 (Why is no real title available?)
• scientific article; zbMATH DE number 3868613 (Why is no real title available?)
• Relativizing relativized computations
• scientific article; zbMATH DE number 4099277 (Why is no real title available?)
• Quantitative Relativizations of Complexity Classes
• scientific article; zbMATH DE number 3940729 (Why is no real title available?)
• scientific article; zbMATH DE number 500314 (Why is no real title available?)
• Separability and one-way functions
• Positive Relativizations of Complexity Classes
• A prioritized information fusion method for handling fuzzy decision-making problems

This page was built for publication: Positive relativizations of the \(P=?\) NP problem

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