Zapiski Nauchnykh Seminarov LOMI
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive
Impact factor

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Zap. Nauchn. Sem. POMI:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Zap. Nauchn. Sem. LOMI, 1988, Volume 174, Pages 122–131 (Mi znsl4514)  

Diophantine complexity

Yu. V. Matijasevich


Abstract: It is well-known that every recursively enumerable set $S$ of natural numbers can be represented as $a\in S\Leftrightarrow \exists x \forall y\leqslant x \exists z_1,…,z_n$ ($D(a,x,y,z_1,…,z_n)=0$) (Davis normal form), as $a\in S\Leftrightarrow \exists z_1,…,z_n$ ($E_1(a,z_1,…,z_n)=E_2(a,z_1,…,z_n)$) (exponential Diophantine representation) and as $a\in S\Leftrightarrow \exists z_1,…,z_n$ ($D(a,z_1,…,z_n)=0$) (Diophantine representation). Each of the above three representations enables us to introduce different complexity measures both of the set $S$ as a whole and of accepting individual members of $S$.
The paper surveys some results by different authors connected with such kinds of complexity measures.

Full text: PDF file (648 kB)

English version:
Journal of Soviet Mathematics, 1991, 55:2, 1603–1610

Bibliographic databases:

UDC: 510.52+511.5

Citation: Yu. V. Matijasevich, “Diophantine complexity”, Computational complexity theory. Part 3, Zap. Nauchn. Sem. LOMI, 174, "Nauka", Leningrad. Otdel., Leningrad, 1988, 122–131; J. Soviet Math., 55:2 (1991), 1603–1610

Citation in format AMSBIB
\Bibitem{Mat88}
\by Yu.~V.~Matijasevich
\paper Diophantine complexity
\inbook Computational complexity theory. Part~3
\serial Zap. Nauchn. Sem. LOMI
\yr 1988
\vol 174
\pages 122--131
\publ "Nauka", Leningrad. Otdel.
\publaddr Leningrad
\mathnet{http://mi.mathnet.ru/znsl4514}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=0976176}
\zmath{https://zbmath.org/?q=an:0724.03027|0679.03016}
\transl
\jour J. Soviet Math.
\yr 1991
\vol 55
\issue 2
\pages 1603--1610
\crossref{https://doi.org/10.1007/BF01098277}


Linking options:
  • http://mi.mathnet.ru/eng/znsl4514
  • http://mi.mathnet.ru/eng/znsl/v174/p122

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Записки научных семинаров ПОМИ
    Number of views:
    This page:191
    Full text:106

     
    Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2022