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