Geodesic
Relativizations of the $P=NP$ problem over the complex number field
Sibirskie èlektronnye matematičeskie izvestiâ, Tome 1 (2004), pp. 91-98.

Voir la notice de l'article provenant de la source Math-Net.Ru

In this article we consider the relativised polynomial complexity classes $P_{\mathbb C}$ and $DNP_{\mathbb C}$ over the complex number field $\mathbb C$, defined in the frames of an approach to generalized computability, considered in [1]. We prove that $P_{\mathbb C}^{\mathbb Z}\ne DNP_{\mathbb C}^{\mathbb Z}$, where the oracle $\mathbb Z$ is the set of integers. 
@article{SEMR_2004_1_a7,
     author = {A. N. Rybalov},
     title = {Relativizations of the $P=NP$ problem over the complex number field},
     journal = {Sibirskie \`elektronnye matemati\v{c}eskie izvesti\^a},
     pages = {91--98},
     publisher = {mathdoc},
     volume = {1},
     year = {2004},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/SEMR_2004_1_a7/}
}
TY  - JOUR
AU  - A. N. Rybalov
TI  - Relativizations of the $P=NP$ problem over the complex number field
JO  - Sibirskie èlektronnye matematičeskie izvestiâ
PY  - 2004
SP  - 91
EP  - 98
VL  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SEMR_2004_1_a7/
LA  - ru
ID  - SEMR_2004_1_a7
ER  - 
%0 Journal Article
%A A. N. Rybalov
%T Relativizations of the $P=NP$ problem over the complex number field
%J Sibirskie èlektronnye matematičeskie izvestiâ
%D 2004
%P 91-98
%V 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SEMR_2004_1_a7/
%G ru
%F SEMR_2004_1_a7
A. N. Rybalov. Relativizations of the $P=NP$ problem over the complex number field. Sibirskie èlektronnye matematičeskie izvestiâ, Tome 1 (2004), pp. 91-98. http://geodesic.mathdoc.fr/item/SEMR_2004_1_a7/

[1] I.V. Ashaev, V.Ya.Belyaev, A.G. Myasnikov, “Podkhody k teorii obobschennoi vychislimosti”, Algebra i logika, 32:4 (1993), 349–386 | MR | Zbl

[2] A.N. Rybalov, “Slozhnost vychislenii v algebraicheskikh sistemakh”, Sibirskii matematicheskii zhurnal, 45:6 (2004), 1365–1377 | MR | Zbl

[3] L. Blum, M. Shub, S. Smale, “On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines”, Bull. Amer. Math. Soc., 21 (1989), 1–46 | DOI | MR | Zbl

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

[5] F. Cucker, M. Matamala, “On digital nondeterminism”, Math. Syst. Theory, 29 (1996), 635–647 | MR | Zbl

[6] T. Emerson, “Relativization of the P=?NP question over the reals (and other ordered rings)”, Theoretical Computer Science, 133 (1994), 15–22 | DOI | MR | Zbl

[7] A. Hemmerling, “Computability and complexity over structures”, Math. Logic Quarterly, 44:1 (1998), 1–44 | DOI | MR | Zbl