Relativized generic classes P and NP

DOI10.17223/20710410/40/8MaRDI QIDQ5151221zbMATH OpenOpenAlexWikidataFDO

Authors Alexander Rybalov

Publication date 17 February 2021

Published in Prikladnaya diskretnaya matematika (Search for Journal in Brave)

Full work available at URL http://mathnet.ru/eng/pdm622

zbMATH Keywords

generic complexityoraclesP vs NP problem

Mathematics Subject Classification ID

Other nonclassical models of computation (68Q09) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• On generic NP-completeness of the Boolean satisfiability problem
• scientific article; zbMATH DE number 3885884
• Computable Dowd-type generic oracles
• An oracle builder's toolkit
• Generic oracles, uniform machines, and codes

Cites work

• Generic-case complexity, decision problems in group theory, and random walks.
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1776257 (Why is no real title available?)
• Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question

Cited in

(9)

• Diagonalizations over polynomial time computable sets
• The generic oracle hypothesis is false
• An oracle builder's toolkit
• Generic separations
• Relativizations of Unambiguous and Random Polynomial Time Classes
• scientific article; zbMATH DE number 3987265 (Why is no real title available?)
• On generic NP-completeness of the Boolean satisfiability problem
• On binary solutions to systems of equations
• On generic complexity of the existential theories

This page was built for publication: Relativized generic classes P and NP

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