arXiv:1702.03152v1 [cs.CC] 10 Feb 2017

A Variation of Levin Search for All Well-Defined
Problems
Fouad B. Chedid
A’Sharqiyah University, Ibra, Oman
f.chedid@asu.edu.om
February 13, 2017
Abstract
In 1973, L.A. Levin published an algorithm that solves any inversion
problem π as quickly as the fastest algorithm p∗ computing a solution for
∗
π in time bounded by 2l(p ) .t∗ , where l(p∗ ) is the length of the binary
∗
∗
encoding of p , and t is the runtime of p∗ plus the time to verify its
correctness. In 2002, M. Hutter published an algorithm that solves any
well-defined problem π as quickly as the fastest algorithm p∗ computing
a solution for π in time bounded by 5.tp (x) + dp .timetp (x) + cp , where
dp = 40.2l(p)+l(tp ) and cp = 40.2l(f )+1 .O(l(f )2 ), where l(f ) is the length
of the binary encoding of a proof f that produces a pair (p, tp ), where
tp (x) is a provable time bound on the runtime of the fastest program p
provably equivalent to p∗ . In this paper, we rewrite Levin Search using
the ideas of Hutter so that we have a new simple algorithm that solves any
well-defined problem π as quickly as the fastest algorithm p∗ computing
a solution for π in time bounded by O(l(f )2 ).tp (x).

keywords: Computational Complexity; Algorithmic Information Theory; Levin
Search.

1

Introduction

We recall that the class N P is the set of all decision problems that can be
solved efficiently on a nondeterministic Turing Machine. Alternatively, N P is
the set of all decision problems whose guessed solutions can be verified efficienlty
on a deterministic Turing Machine, or equivalently today’s computers. The
interesting part is that the set of all hardest problems in the class N P (also
known as N P -complete problems) have so far defied any efficient solutions on
real computers. This has been a very frustrating challenge given that many
of the N P -complete problems are about real-world applications that we really
would like to be able to solve efficiently.

1

Leonid Levin [6], and independently from Stephen Cook [1], defined the class
N P , identified the class N P -complete, and gave a few reductions that show the
N P -completeness of some N P problems (independent from the work of Richard
Karp [3]). In that same paper [6], Levin gave an algorithm to deal with N P complete problems provided that someone develops a proof that shows P = N P .
In this case, Levin’s algorithm can be used to develop a polynomial-time solution
for every N P -complete problem. In particular, Levin’s algorithm works with
a very broad class of mathematical problems that can be put in the form of
inverting easily computable functions. For example, suppose we have a function
y = f (x), where we know nothing about f except that it is easily computable.
The challenge is to find x = f −1 (y) and to do so in a minimal amount of time.
The idea of Levin’s algorithm is to go through the space of all algorithms in
search for a fastest algorithm A that knows the secret of f . In general, let π be
an inversion problem and let p∗ be a known fastest algorithm for π that runs in
time t∗ , where t∗ is the runtime of p∗ plus the time to verify its correctness. The
Universal Search algorithm of Levin, also known as Levin Search, is an effective
∗
procedure for findng p∗ in time bounded by 2l(p ) .t∗ , where l(p∗ ) is the length
of the binary encoding of p∗ . Levin Search can also be used with some forms
of optimization and prediction problems, and it is theoretically optimal. The
following is a pseudocode for Levin Search:
Pseudocode Levin Search
t = 2.
for all programs p, in parallel, do
run p for at most t.2−l(p) steps
if p is proved to generate a correct solution for π, then return p for p∗ and
halt.
endfor
t = 2.t
goto for all programs p
End of Pseudocode
The idea of Levin Search is to search the space of all programs p in increasing order of l(p) + log t, or equivalently in decreasing order of P rob.(p)
, where
t
P rob.(p) = 2−l(p) is the probability contributed to p in the overall Solomonoff’s
algorithmic probability [8] of finding a solution for π. By construction, P rob.(p)
gives short programs a better chance of being successful on the assumption that
short programs are more worthy (Occam’s razor). We mention that the main
idea of Levin Search was behind the notion of Levin Complexity, which defines
a computable version of Kolmogorov complexity based on time-bounded Turing machines. Let U be a fixed reference universal Turing machine, the Levin
complexity of a finite binary string x is defined as
Kt (x) = min .p {l(p) + log t : U (p) = x, in at most t steps.}
Returning to Levin Search, during each iteration of the “for” loop, each program
2

is assigned a fraction of time proportional to its probability, which basically says
that short programs get to run more often.
The rest of this paper is organized as follows. Section 2 describes a sequential
implementation of Levin Search and shows that it solves any inversion problem
π as quickly as the fastest algorithm p∗ computing a solution for π, save for a
∗
factor of 2l(p ) . Section 3 describes an improvement on Levin Search for all welldefined problems. A problem is designated as well-defined if its solutions can
be formally proved correct and have provably quickly computable time bounds.
This improvement, known as Hutter’s algorithm [2], describes an algorithm that
solves any well-defined problem π as quickly as the fastest algorithm computing
a solution for π, save for a factor of 5. Section 4 contains our contribution. We
rewrite Levin Search using the ideas of Hutter so that we have a new simple
algorithm that solves any well-defined problem π as quickly as the fastest algorithm p∗ computing a solution for π, save for a factor of O(l(f )2 ), where l(f ) is
the length of the binary encoding of a proof f that produces a pair (p, tp ), where
tp is a provable time bound on the runtime of the fastest program p provably
equivalent to p∗ . Section 5 contains some concluding remarks.

2

Sequential Levin Search

The pseudocode of Levin Search from the previous section cannot be readily executed on today’s computers. A sequential version of Levin Search can simulate
the parallel execution of all programs by running programs, each for a fraction
of time, one after another, in increasing order of their length. Hereafter, we
assume that all progams are encoded using prefix-free codes, using for example,
Shannon-Fano coding [9]. Let π be an inversion problem and let p∗ be a known
fastest algorithm for π that runs in time t∗ , where t∗ is the runtime of p∗ plus
the time to verify its correctness. Also, let l(p) be the length of the binary
encoding of program p.
Algorithm Levin Search
t = 2;
for all programs p of length l(p) = 1, 2, . . . , log t do
run p for at most t.2−l(p) steps.
if p is proved to generate a correct solution for p, return p for p∗ and halt.
endfor
t = 2.t
goto for all programs p
End of Levin Search
During each time step t, the algorithm runs all programs p of length ≤ log t
in increasing order of their length and gives each program p a fraction of time
proportional to 2−l(p) .
Time Analysis. The following proof for the runtime complexity of Levin
Search is due to Solomonoff [7]. The “for” loop in the algorithm takes time

3

P

t.2−l(p) ≤ t. This is true by Kraft inequality [5]. Now, suppose that

p:l(p)≤log t

Levin Search stops at time t = T . Then, the total runtime of this algorithm is
timeLevinSearch ≤ 2 + 4 + . . . +

T
T
+ + T = 2T − 2 < 2T.
4
2

Moreover, the runtime t∗ of p∗ is
∗

t∗ = T.2−l(p

)

>

timeLevinSearch −l(p∗ ).
.2
2

Thus,

∗

timeLevinSearch < 2l(p

)+1 ∗

.t = O(t∗ )
∗

This is true because the multiplicative constant 2l(p )+1 is independent of the instance of the problem π. We mention that it is this huge multiplicative constant
that limits the applicability of Levin Search in practice.
It seems that a possible way to improve the runtime of Levin Search is to
find a way, where not all programs of length ≤ log t get executed, for each value
of t. Ideally, we would like a way that executes at most a single program for
each value of t, preferably a shortest and fastest one, and this is exactly what
we will present in Section 4.

3

Hutter’s Fastest and Shortest Algorithm for
All Well-Defined Problems

In [2], Hutter presented an improvement on Levin Search for problems that are
well-defined. By this, Hutter means a problem whose solutions can be formally
proved correct and have provably quickly computable time bounds. Let p∗ (x) be
a known fastest algorithm for some well-defined problem π(x). Then, Hutter’s
algorithm will construct a solution p(x) that is provably equivalent to p∗ (x), for
all x, in time proportional to 5.tp (x) + d.timetp (x) + c, where tp (x) is a provable
time bound on the runtime of p(x), timetp (x) is the time needed to compute
tp (x), and d and c are constants which depend on p but not on π(x). This shows
that Hutter’s agorithm runs in time O(tp ), save for a factor of 5.
Our work in the next section is inspired by the ideas of Hutter, and so, for
completeness, we have included below the details of Hutter’s algorithm as they
appear in [2].
The main idea of Hutter’s algorithm is to search the space of all proofs1 in
some formal axiomatic system, and not the space of all programs. In particular,
the algorithm searches for those proofs that can tell us which programs are
provably equivalent to p∗ and have provably quickly computable time bounds.
This is doable since the set of all proofs in any formal sysem is enumerable.
1 Given a formal logic system F with a set of axioms and inference rules. A proof in F is
a sequence of formulas, where each formula is either an axiom in F or is something that can
be inferred using F ’s axioms and inference rules, and previoulsy inferred formulas.

4

Moreover, in [2], Hutter showed how to formalize the notions of provability,
Turing Machines, and computation time. Let U be a fixed reference Universal
Turing machine. For finite binary strings p and tp , we assume that
• U (p, x) computes the output of program p on input x.
• U (tp , x) returns a time bound on the runtime of program p on input x.
Moreover, Hutter defined the following two terms:
• A term u is defined such that the formula [∀y : u(p, y) = u(p∗ , y)] is true
if and only if U (p, x) = U (p∗ , x), ∀x.
• A term tm is defined such that the formula [tm(p, x) = n] is true if and
only if U (p, x) takes n steps; that is, if timep (x) = n.
Then, we say that programs p and p∗ are provably equivalent if the formula
[∀y : u(p, y) = u(p∗ , y)] can be proved.
The algorithm of Hutter is as follows.
Algorithm Hutter(x)
Let L = φ, tf ast = ∞, and pf ast = p∗ .
Run A,B, and C concurrently with 10%, 10%, and 80% of computational resources, respectively.
Algorithm A
{ This algorithm identifies programs p that are provably equivalent to p∗ and
have provably computable time bounds tp }
for i = 1, 2, 3, . . . do
pick the ith proof in the list of all proofs and
if the last formula in the proof is equal to [∀y, u(p∗ , x) = u(p, y) and
u(tp , y) ≥ tm(p, y)], for some pair of strings (p, tp ) then
Let L = L ∪ {(p, tp )}.
End A
Algorithm B
{ This algorithm finds the program with the shortest time bound in L.}
for all (p, tp ) in L do
run U on all (tp , x) in parallel for all tp with relative computational
resources 2−l(p)−l(tp ) .
if U halts for some tp and U (tp , x) < tf ast then
tf ast = U (tp , x) and pf ast = p.
endfor all (p, tp )
End B
Algorithm C
For k = 1, 2, 4, 8, . . . do
pick the currenlty fastest program pf ast with time bound tf ast .
run U on (p, x) for k steps.
5

if U halts in less than k steps, then print result U (p, x) and abort computation
of A, B, and C.
endfor k
End C
In [2], it was shown that the overall runtime of Hutter’s algorithm is
timeHutter (x) ≤ 5.tpf ast (x) + dp .timetpf ast (x) + cp ,
where dp = 40.2l(pf ast )+l(tpf ast ) and cp = 40.2l(proof (pf ast ))+1 .O(l(proof (pf ast )2 ).

4

A Variation of Levin Search Inspired by the
Fastest and Shortest Algorithm of Hutter

We rewrite Levin Search so that it searches, in parallel, the space of all proofs,
and not the space of all programs. Let p∗ be a known fastest algorithm for some
well-defined problem π. Then, our algorithm will construct a solution p(x), for
all x, that is provably equivalent to p∗ (x) in time O(tp (x)), save for a factor of
O(l(proof (p))2 ), where tp (x) is a provable time bound on the runtime of the
fastest program p provably equivalent to p∗ .
We assume a formal axiomatic system F and the same terms u and tm defined in
Hutter’s algorithm. Moreover, we assume
all pairs (p, tp ) are encoded using
P that
prefix-free codes, and hence, we have
2−l(p)−l(tp ) ≤ 1, by Kraft inequality.
(p,tp )

The following is our Modified Levin Search algorithm:
Algorithm Modified Levin Search(x)
t = 2; tf ast = ∞; pf ast = λ; { pf ast is initialized to the empty string }
for all proofs f ∈ F of length l(f ) = 1, 2, . . . , log t do
write down the first t.2−l(f ) characters of proof f .
if the last formula in these characters is equal to ∀y, u(p∗ , x) = u(p, y)
and u(tp , y) ≥ tm(p, y), for some pair of strings (p, tp ) then
run tp (x) for at most t.2−l(p)−l(tp ) steps.
if tp halts and tp (x) < tf ast then
tf ast = tp (x) and pf ast = p.
endfor
if pf ast 6= λ then
run pf ast for at most t steps with time bound tf ast .
if pf ast (x) halts, then return pf ast for p∗ and halt.
endif
t = 2t.
go to for all proofs f ∈ F
End of Modified Levin Search
6

We note that during each time step t, Modified Levin Search runs at most a
single provably fast program pf ast that is provably equivalent to p∗ .
Running time calculation: Following [2], let naxioms be the finite number
of axioms in F. Then, each proof f ∈ F is a sequence F1 F2 . . . Fn , for some
positive integer n, where each Fi (1 ≤ i ≤ n) is either an axiom or a formula in
F. It takes O(naxioms .l(Fi )) time to check if Fi is an axiom, and O(l(f )) time to
check if Fi is a formula that can be inferred from other formulas Fj ∈ f , j < i.
Thus, checking the validity of all formulas in f , and hence the validity of the
proof f , takes O(l(f )2 ) time.
The “for” loop in Modified Levin Search takes time
X
O(t.2−l(f ) ) + O((t.2−l(f ) )2 ) + t.2−l(p)−l(tp )
t1 =
f :l(f )≤log t

X

≤t+

O(l(f )) + O(l(f )2 )

f :l(f )≤log t

This is true because

P

2−l(p)−l(tp ) ≤ 1, by Kraft inequality. we next have

(p,tp )

t1 ≤ t +

X

O(l(f )2 )

f :l(f )≤log t

< t + 2log t+1 .O(l(f ′ )2 )
< t + 2t.O(l(f ′ )2 )
< O(l(f ′ )2 ).t,
where f ′ is the proof that procuded the pair (p, tp ) with the shortest provable
time bound tp (x), among all proofs of length ≤ log t.
Thus, the runtime of Modified Levin Search is equal to
X
timeModif iedLevinSearch =
O(l(f ′ )2 ).t + t
t=2

=

X

<

X

O(l(f ′ )2 ).t

t=2

O(l(f ∗ )2 ).t,

t=2

where l(f ∗ ) is the length of the binary encoding of the proof that produced the
resultant pair (pf ast , tpf ast ).

7

Suppose that Modified Levin Search stops at time t = T ≤ tpf ast (x).Then
timeModif iedLevinSearch (x) = O(l(f ∗ )2 )}.(2 + 4 + . . . + T /2 + T )
= O(l(f ∗ )2 ).(2T − 2)
< O(l(f ∗ )2 ).2T
= O(l(f ∗ )2 ).T
≤ O(l(f ∗ )2 ).tpf ast (x).
This shows that Modified Levin Search runs in time O(tpf ast ), save for a factor
of O(l(f ∗ )2 ).

5

Concluding Remarks

We recall that Hutter’s algorithm was designed for well-defined problems. These
are problems the solutions of which can be formally proved correct and have
provably quickly computable time bounds. For programs provably correct (they
halt and compute the correct answer), but for which no quickly computable
time bounds exist (For example, the traveling salesman problem), Hutter [2]
explained that an obvious time bound for a progam p is its actual running time
timep (.). By replacing tp (.) with timep (.) in the runtime of Hutter’s algorithm,
and by noticing that, in this case, timetp (x) becomes timetimep (x) ≤ timep (x),
we have
timeHutter (x) ≤ 5.tp (x) + dp .timetp (x) + cp
≤ 5.timep (x) + dp .timep (x) + cp
≤ (5 + dp ).timep (x) + cp
≤ (5 + 40.2l(p) ).timep (x) + 40.2l(f )+1 .O(l(f )2 )
where l(p) is the length of the binary encoding of p, and l(f ) is the length of the
binary encoding of a proof f that produces the program p that is provably equivalent to the fastest known algorithm p∗ for the problem in hand. Thus, for such
programs, Hutter’s algorithm is optimal, save for a huge constant multiplicative
term and a huge constant additive term.
We next calculate the runtime of our algorithm in case we are dealing with
programs that can be provably correct, but for which no quickly computable
time bounds exist. Suppose that our algorithm stops at time t = T . Then, we
have
timeModif iedLevinSearch < O(l(f )2 ).T.
We also have timep (x) = T.2−l(p) . Thus,
timeModif iedLevinSearch < O(l(f )2 ).2l(p) .timep (x)

8

Thus, for such programs, the runtime of our algorithm also suffers from a huge
constant multiplicative term, but with no additinoal huge additive terms.
We conclude this paper by recalling an approach, proposed by Solomonoff in
1985 [7], to manage the huge multiplicative constant in the big-oh notation of the
running time of Levin Search. We do so because we think that the importance
of that work of Solomonoff is not widely appreciated. Solomonoff argued that
if machines are going to have a problem solving capability similar to that of
humans, then machines cannot start from scratch everytime they attempt to
solve a new problem. We, humans, rely on our previous knolwedge of solutions
to other problems to figure out a solution for a new problem. The basic idea
of Solomonoff is that we should be able to construct p∗ via a list of references
to previously discovered solutions for other related problems. We can imagine
writing the code for p∗ as p1 p2 . . . pn , where pi is a reference to a solution for
problem πi stored on a separate work tape of a Kolmogorov-Uspensky Machine
[4]. This way, the solution p∗ is a sequence of calls to other solutions stored on
the work tapes. This way, the length of p∗ would be made significantly smaller
than the sum of the lengths of pi , and the saving in the length of p∗ would
exponentially decrease the multiplicate constant in the big-oh notation of Levin
Search.

References
[1] S. A. Cook, The complexity of theorem-proving procedures, Proceedings
of the Third Annual ACM Symposium on Theory of Computing. (1971)
151–158.
[2] M. Hutter, The fastest and shortest algorithm for all well-defined problems,
International Journal of Foundations of Computer Science. 13:3 (2002)
431–443.
[3] R. M. Karp, Reducibility among combinatorial problems, In R.E. Miller
and J.W. Thatcher (editors). Complexity of Computer Computations.
(1972) 85–103.
[4] A.N. Kolmogorov and V.A. Uspenski, On the definition of an algorithm,
Uspehi Mat. Nauk. 13 (1958), 3–28. AMS Transl. 2nd ser.29 (1963) 217–
245.
[5] L.G. Kraft, A device for quantizing, grouping, and coding amplitude modulated pulses, MS Thesis, Electrical and Engineering Department, MIT.
[6] L. A. Levin, Universal sequential search problems, Problemy Peredaci Informacii. 9 (1973) 115–116. Translated in Problems of Information Transmission. 9 (1973) 265–266.
[7] R. J. Solomonoff, Optimum sequential searh. (1985) 1–13.

9

[8] R. J. Solomonoff, A formal theory of inductive inference: Part 1 and 2,
Inform. Control. 7 (1964) 1–22, 224–254.
[9] C.E. Shannon, A mathematical theory of communication, Bell System
Technical Journal. 27 (1948) 379–423.

10

