Positive relativizations of the P=? NP problem

DOI10.1016/0022-0000(89)90014-7zbMATH Open0678.68045OpenAlexW2078408075MaRDI QIDQ1124342FDOQ1124342

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

Recommendations

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

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)

Cites Work

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

Cited In (23)

• Honest polynomial time reducibilities and the \(P=?NP\) problem
• 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
• Characterizing polynomial complexity classes by reducibilities
• Qualitative relativizations of complexity classes
• Title not available (Why is that?)
• Relativized alternation and space-bounded computation
• The structure of relativized P and NP questions
• Title not available (Why is that?)
• On a criterion of NP-completeness
• Cook reducibility is faster than Karp reducibility in NP
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Relativizing relativized computations
• Quantitative Relativizations of Complexity Classes
• Title not available (Why is that?)
• Title not available (Why is that?)
• 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)