Информационная система "Конференции"

Abstracts

Computability theory

A theory of computation and computational complexity over fields of complex and real numbers was introdused in [1]. In [2,3,4] this theory was generalized to arbitrary algebraic structure. It has appeared, that many facts of the classical theory of algorithms and computation complexity remain true in this generalized theory. Moreover in some algebraic systems these results are proved much easier than the classical prototypes.

This report is devoted to transfer of classical result of Baker, Gill and Solovay ([5]) to complex number field C. Baker-Gill-Solovay theorem states that there exists an oracle A, for which relativised classes P^A and NP^A are different. The author of the report in [6] proved for C that P^Z is not equals DNP^Z (analog of NP class for field C), there Z is the set of integers. Baker-Gill-Solovay oracle is the recursive set, but Z is not recursive over C in the sence of generalized computability. So the question arises about existence of a recursive oracle for this separation.

The following theorem gives an example of that oracle.

Theorem. Let BZ is the set

{ (a₁,...,a_n) : all a_i are integers and |a_i|< 2²ⁿ }.

Then the classes P^BZ and DNP^BZ over C are different.

References

[1] 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, pp. 1-46, 1989.

[2] Ашаев И.В., Беляев В.Я., Мясников А.Г. Подходы к теории обобщенной вычислимости // Алгебра и логика, Т.32, № 4, С. 349-386, 1993.

[3] Hemmerling A. Computability and complexity over structures // Math. Logic Quarterly, 44, № 1, pp. 1-44, 1998.

[4] Рыбалов А.Н. Сложность вычислений в алгебраических системах // Сибирский математический журнал, Т.45, № 6, С. 1365-1377, 2004.

[5] Baker T., Gill J., Solovay R. Relativizations of the P=?NP question // SIAM Journal on Computing, 4, pp. 431-442, 1975.

[6] Рыбалов А.Н., Релятивизации вопроса P=NP над полем комплексных чисел // Сибирские электронные математические известия, Т. 1, С. 91-98, 2004.

Mail to Webmaster alc9@math.nsc.ru

|Home Page| |English Part|

Go to Home