RUS  ENG
Full version
JOURNALS // Sibirskie Èlektronnye Matematicheskie Izvestiya [Siberian Electronic Mathematical Reports] // Archive

Sib. Èlektron. Mat. Izv., 2004 Volume 1, Pages 91–98 (Mi semr8)

This article is cited in 1 paper

Research papers

Relativizations of the $P=NP$ problem over the complex number field

A. N. Rybalov

Omsk State University

Abstract: 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.

UDC: 510.52, 510.57

MSC: 03D60, 68Q15

Received September 15, 2004, published November 22, 2004



Bibliographic databases:


© Steklov Math. Inst. of RAS, 2026