RUS  ENG
Полная версия
ЖУРНАЛЫ // Сибирские электронные математические известия // Архив

Сиб. электрон. матем. изв., 2004, том 1, страницы 91–98 (Mi semr8)

Эта публикация цитируется в 1 статье

Статьи

Релятивизации вопроса $P=NP$ над полем комплексных чисел

А. Н. Рыбалов

Омский государственный университет

Аннотация: 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.

УДК: 510.52, 510.57

MSC: 03D60, 68Q15

Поступила 15 сентября 2004 г., опубликована 22 ноября 2004 г.



Реферативные базы данных:


© МИАН, 2024