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

Search
RSS
Latest issue
Current issues
Archive issues
What is RSS



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



Search through the site:
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 7 papers

Сorrespondence


PDF version     HTML version

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.

UDC: 519.14

Received: 07.06.1972

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

Citation in format AMSBIB:
\Bibitem{1}
\by L.~A.~Levin
\paper Universal Sequential Search Problems
\jour Probl. Peredachi Inf.
\yr 1973
\vol 9
\issue 3
\pages 115--116
\mathnet{ppi914}


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

    Full text (in Russian): PDF file (306 kB)

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

    Review databases:

    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 artiles:
    1. М. Х. Айзенштейн, “О существовании оптимальных алгоритмов для комбинаторных задач и языков”, УМН, 35:5(215) (1980), 221–222      ; M. Kh. Aizenshtein, “On the existence of optimal algorithms for combinatorial problems and languages”, Russian Math. Surveys, 35:5 (1980), 249–250  
    2. А. О. Слисенко, “Сложностные задачи теории вычислений”, УМН, 36:6(222) (1981), 21–103      ; A. O. Slisenko, “Complexity problems in computational theory”, Russian Math. Surveys, 36:6 (1981), 23–125  
    3. П. Витаньи, М. Ли, “Колмогоровская сложность: двадцать лет спустя”, УМН, 43:6(264) (1988), 129–166      
    4. Л. А. Левин, “Односторонние функции”, Пробл. передачи информ., 39:1 (2003), 103–117      ; L. A. Levin, “One-Way Functions”, Problems Inform. Transmission, 39:1 (2003), 92–103  
    5. V. Kreinovich, M. Margenstern, “In some curved spaces, one can solve NP-hard problems in polynomial time”, Исследования по конструктивной математике и математической логике. XI, Зап. научн. сем. ПОМИ, 358, ПОМИ, СПб., 2008, 224–250  
    6. А. Д. Коршунов, “Некоторые нерешенные задачи дискретной математики и математической кибернетики”, УМН, 64:5(389) (2009), 3–20  
    7. А. А. Кожевников, С. И. Николенко, “О полных односторонних функциях”, Пробл. передачи информ., 45:2 (2009), 101–118    ; A. A. Kozhevnikov, S. I. Nikolenko, “On complete one-way functions”, Problems Inform. Transmission, 45:2 (2009), 168–183  
  • Проблемы передачи информации Problems of Information Transmission
    Number of views:
    This page:378
    Full text:119
    First page:4
     
    Contact us:
     Terms of Use  Registration © Steklov Mathematical Institute RAS, 2010
    © Branch of Mathematical Sciences, Russian Academy of Sciences, 2010