RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PERSONAL OFFICE
General information
Latest issue
Archive
Impact factor

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Probl. Peredachi Inf.:
Year:
Volume:
Issue:
Page:
Find






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


Probl. Peredachi Inf., 1973, Volume 9, Issue 3, Pages 115–116 (Mi ppi914)  

This article is cited in 11 scientific papers (total in 11 papers)

Сorrespondence

Universal Sequential Search Problems

L. A. Levin


Abstract: Several well-known large-scale problems of the “sequential search” type are discussed, and it is proved that those problems can be solved only in the time that it takes to solve any problems of the indicated type, in general.

Full text: PDF file (306 kB)

English version:
Problems of Information Transmission, 1973, 9:3, 265–266

Bibliographic databases:

UDC: 519.14
Received: 07.06.1972

Citation: L. A. Levin, “Universal Sequential Search Problems”, Probl. Peredachi Inf., 9:3 (1973), 115–116; Problems Inform. Transmission, 9:3 (1973), 265–266

Citation in format AMSBIB
\Bibitem{Lev73}
\by L.~A.~Levin
\paper Universal Sequential Search Problems
\jour Probl. Peredachi Inf.
\yr 1973
\vol 9
\issue 3
\pages 115--116
\mathnet{http://mi.mathnet.ru/ppi914}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=340042}
\zmath{https://zbmath.org/?q=an:0313.02026}
\transl
\jour Problems Inform. Transmission
\yr 1973
\vol 9
\issue 3
\pages 265--266


Linking options:
  • http://mi.mathnet.ru/eng/ppi914
  • http://mi.mathnet.ru/eng/ppi/v9/i3/p115

    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

    This publication is cited in the following articles:
    1. M. Kh. Aizenshtein, “On the existence of optimal algorithms for combinatorial problems and languages”, Russian Math. Surveys, 35:5 (1980), 249–250  mathnet  crossref  mathscinet  zmath  adsnasa  isi
    2. A. O. Slisenko, “Complexity problems in computational theory”, Russian Math. Surveys, 36:6 (1981), 23–125  mathnet  crossref  mathscinet  zmath  adsnasa  isi
    3. P. Vitani, M. Li, “Kolmogorovskaya slozhnost: dvadtsat let spustya”, UMN, 43:6(264) (1988), 129–166  mathnet  mathscinet  zmath
    4. L. A. Levin, “One-Way Functions”, Problems Inform. Transmission, 39:1 (2003), 92–103  mathnet  crossref  mathscinet  zmath
    5. J. Math. Sci. (N. Y.), 158:5 (2009), 727–740  mathnet  crossref  elib
    6. E. A. Hirsch, D. Yu. Grigor'ev, K. V. Pervyshev, “Time hierarchies for cryptographic function inversion with advice”, J. Math. Sci. (N. Y.), 158:5 (2009), 633–644  mathnet  crossref
    7. A. D. Korshunov, “Some unsolved problems in discrete mathematics and mathematical cybernetics”, Russian Math. Surveys, 64:5 (2009), 787–803  mathnet  crossref  crossref  mathscinet  zmath  adsnasa  isi  elib  elib
    8. A. A. Kozhevnikov, S. I. Nikolenko, “On complete one-way functions”, Problems Inform. Transmission, 45:2 (2009), 168–183  mathnet  crossref  mathscinet  zmath  isi
    9. S. I. Nikolenko, D. S. Tugaryov, “A complete one-way function based on a free finite rank $\mathbb Z\times\mathbb Z$-module”, J. Math. Sci. (N. Y.), 192:3 (2013), 307–315  mathnet  crossref  mathscinet
    10. V. N. Zakharov, V. A. Kozmidiadi, “On relationships between complexity classes of Turing machines”, Comput. Math. Math. Phys., 57:4 (2017), 726–738  mathnet  crossref  crossref  mathscinet  isi  elib
    11. D. E. Gorbatenko, A. A. Semënov, “Protivodeistvie sgovoru v diskretnykh dinamicheskikh modelyakh kompyuternykh setei”, UBS, 75 (2018), 76–102  mathnet
  • Проблемы передачи информации Problems of Information Transmission
    Number of views:
    This page:5134
    Full text:3259
    First page:4

     
    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2018