Geodesic
Relativized generic classes $\mathrm P$ and $\mathrm{NP}$
Prikladnaâ diskretnaâ matematika, no. 2 (2018), pp. 100-104 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

Classical theorem of Baker, Gill and Solovay states that there exist two oracles $A$ and $B$ such that $\mathrm P^A=\mathrm{NP}^A$, but $\mathrm P^B\neq\mathrm{NP}^B$. This result indicates that the classical tools of computability theory (such as diagonalization) are inapplicable to prove the inequality $\mathrm P\neq\mathrm{NP}$. Generic-case approach to algorithmic problems was suggested by Miasnikov, Kapovich, Schupp and Shpilrain in 2003. This approach studies behavior of an algorithm on typical (almost all) inputs and ignores the rest of inputs. Many classical undecidable or hard algorithmic problems become feasible in the generic case. In this paper we introduce generic analogs $\mathrm{genP}$ and $\mathrm{genNP}$ of the classical computational complexity classes $\mathrm P$ and $\mathrm{NP}$. We prove a generic analog of the Baker–Gill–Solovay theorem: there exist two oracles $A$ and $B$ such that $\mathrm{genP}^A=\mathrm{genNP}^A$, but $\mathrm{genP}^B\neq\mathrm{genNP}^B$. Therefore the diagonalization arguments cannot be applied to prove the inequality $\mathrm P\neq\mathrm{NP}$ in the generic case too.
Keywords: generic complexity, $\mathrm P$ vs $\mathrm{NP}$ problem
Mots-clés : oracles. 
@article{PDM_2018_2_a7,
     author = {A. N. Rybalov},
     title = {Relativized generic classes~$\mathrm P$ and~$\mathrm{NP}$},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {100--104},
     year = {2018},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2018_2_a7/}
}
TY  - JOUR
AU  - A. N. Rybalov
TI  - Relativized generic classes $\mathrm P$ and $\mathrm{NP}$
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2018
SP  - 100
EP  - 104
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/PDM_2018_2_a7/
LA  - ru
ID  - PDM_2018_2_a7
ER  - 
%0 Journal Article
%A A. N. Rybalov
%T Relativized generic classes $\mathrm P$ and $\mathrm{NP}$
%J Prikladnaâ diskretnaâ matematika
%D 2018
%P 100-104
%N 2
%U http://geodesic.mathdoc.fr/item/PDM_2018_2_a7/
%G ru
%F PDM_2018_2_a7
A. N. Rybalov. Relativized generic classes $\mathrm P$ and $\mathrm{NP}$. Prikladnaâ diskretnaâ matematika, no. 2 (2018), pp. 100-104. http://geodesic.mathdoc.fr/item/PDM_2018_2_a7/

[1] Baker T., Gill J., Solovay R., “Relativizations of the P=?NP question”, SIAM J. Computing, 4 (1975), 431–442 | DOI | MR | Zbl

[2] Vyalyi M., Kitaev A., Shen A., Classical and Quantum Computation, Graduate Studies in Mathematics, AMS, 2002, 272 pp. | MR | Zbl

[3] Garey M., Johnson D., Computers and Intractability, Freeman Co, N.Y., 1979, 340 pp. | MR | MR | Zbl

[4] Kapovich I., Miasnikov A., Schupp P., Shpilrain V., “Generic-case complexity, decision problems in group theory and random walks”, J. Algebra, 264:2 (2003), 665–694 | DOI | MR | Zbl