“Universal Sequential Search Problems”, 1973 (; backlinks; similar):
[on Levin’s universal search; for English discussion, see 1984]
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.
View PDF: