The fastest and shortest algorithm for all well-defined problems (2002) | Hacker News Reader

The fastest and shortest algorithm for all well-defined problems (2002)

researchgate.net

119 pointspengstrom24 comments

Here's the arxiv link: https://arxiv.org/abs/cs/0206022

(for anyone who shares my pet hatred for researchgate)

OMG yes. The "gate" in its name is really apt. ResearchGate adds zero value but non-zero barriers to access.

It never occurred to me how hilarious the name "ResearchGate" is

>An interesting and counter-intuitive consequence of Theorem 1, derived in Section 7, is that the fastest program that computes a certain function is also among the shortest programs that provably computes this function. Looking for larger programs saves at most a ﬁnite number of computation steps, but cannot improve the time order.

Pretty cool paper, it's from 2002 that's amazing. I'm having trouble locating the factor of five explanation. Why 5? Is it just the safest lowest bound they could guarantee without too much prodding?

It's the lowest they could find.

From section 5: The factor of 5 may be reduced to 4 + ε by assigning a larger fraction of time to algorithm C. The constants cp and dp will then be proportional to 1/ε. We were not able to further reduce this factor.

It's a purely arbitrary number, arising from the choice of an 80/20 division of CPU cycles between exploring and exploiting. You have to choose some number; pretty much any choice would work more or less equally well here, though there is a sense in which 2 would be the simplest/most natural choice.

I don't understand why it's supposedly counter-intuitive that the fastest code is also amongst the shortest. Makes perfect sense to me?

This paper is by Marcus Hutter, the same person who founded the Hutter Prize for data compression in 2006. https://en.wikipedia.org/wiki/Hutter_Prize

The conclusion contains an interesting question:

    Will the ultimate search for asymptotically fastest programs typically lead to fast or slow programs for arguments of practical size? Levin search, matrix multiplication and the algorithm Mp∗ seem to support the latter, but this might be due to our inability to do better.

Asymptotic complexity analysis is kind of broken, there's more of a tradeoff in using different algorithms than "\Theta(n) is better than \Theta(n \log n)" would indicate.

I wonder if a better framework exists, but that's probably several open research topics bundled in a single question.

Yes, it offends my aesthetic sense when the asymptotically fastest algorithms for simple problems are complex monsters. It didn't used to be like that: early fast algorithms (like heapsort and FFT) are only very slightly more complex than the naive ones.

Computer science was a new branch of mathematics 100 years ago. Folks discovered the easy, low-lying algorithms. I don't know about you, but I've rediscovered quite old results that are named so-and-so's algorithm or what's-their-face's theorem; because they were the obviously efficient ways of solving those problems.

Supposing P=NP, one would expect the polytime algorithm to be brain-meltingly complex. Same goes for, say, a n^2log(n) matrix multiplication algorithm.

Simplification is a really good strategy for optimizing algorithms. But sometimes, doing less work requires doing a bit of thinking upfront, or carefully cleaning up behind yourself (but not cleaning too eagerly).

I really don’t understand why this is being downvoted. Beyond trivial algorithms, as mentioned in the parent, fast algorithms come from deep knowledge of the problem, leading to highly tailored data structures, and thus very complicated algorithms. I’m not sure why this is controversial? Also citing aesthetic sensibility is fine, but it’s also fine to update or recalibrate one’s aesthetic intuition.

lol cooley-tukey FFT is anything but simple when you actually have to implement it.

Cooley-Tukey Fast Fourier Transform can be complex to implement, if you want to optimize it. A basic version is surprisingly simple, I implemented it for fun in Python a couple of years ago:

    def fft(x):
        N = len(x)
        if N == 1:
            return x
        assert N % 2 == 0
        E = fft(x[::2])
        O = fft(x[1::2])
        X = [None] * N
        for k in range(N // 2):
            tf = np.exp(-2j * np.pi * k / N)
            X[k] = E[k] + tf * O[k]
            X[k + N//2] = E[k] - tf * O[k]
        return X

The Wikipedia article describing it is surprisingly decent: https://en.wikipedia.org/wiki/Cooley%E2%80%93Tukey_FFT_algor...

I remember showing a coworker a complexity analysis I did, where I'd written "0.002 n lg n + 3n". I was surprised when they asked "why did you put the insignificant one first?" but then realized... that's exactly right! Even for universe sized problems, 3n is more than 0.002 n lg n.

Basically, as soon as you care enough about constant factors to actually compute them, some of your habits from doing asymptotic analysis can be actively harmful.

FTA:

> This work could be viewed as another O() warning showing how important factors and even subdominant additive terms are.

I’m always surprised that more research doesn’t start from the mathematical “end” and work backwards to something that approximates it.

For instance, assuming our universe is computable (or at least can be approximated to a high degree as computable), we know that Solomonoff induction is in some sense a mathematical upper bound on the best we could do at predicting the future.

If we had a magical program that, given a sequence of data S, found the shortest (prefix free, non-halting) program that produced S, we would essentially have real AI (and the “best” AI, in some mathematical sense on general optimality over other algorithms).

We know this is uncomputable, but I’m surprised that this fact seems to totally throw a wrench into at least approximating it. I suppose some efforts in reinforcement learning could sort of be considered attempts at this, but not really in the sense of mathematically developing the best physical implementation to solving the problem.

One thing to keep in mind with all these "Universal AI" ideas (Hutter Search, Levin Search, Goedel Machines, etc.) is that they make very few assumptions about the task. That's their strength, but it's also what makes them hopelessly inefficient. We can get massive speedups by introducing a bit more structure, e.g. inverting differentiable functions rather than all functions makes it practical to use neural networks and their like; inverting convex functions lets us do simple hill climbing; etc.

In the case of Hutter Search specifically, we could get much more promising results if we're willing to throw away Turing Completeness. For example, it's easier to find provable optimisations if we're dealing with regexps rather than arbitrary programs. Of course, such "easy" systems tend to have fast approaches already.

I think there's definitely a role for these algorithms, but mostly as an "outer loop"; similar to using grid-search to find good hyperparameters of an ML model; or how we often throw genetic algorithms at tasks which have no 'obviously correct' solution (like choosing the architecture of a neural network)

I like to think of this as the "ultimate JIT compiler": when we start executing a program, we run an optimiser in parallel. Hence the longer the program takes, the longer we spend optimising it; this focuses our optimisation efforts, similar to how JITs only kick in after functions have been called a certain number of times.

The main difference between Hutter's algorithm and a JIT compiler is that JITs operate locally on small pieces of a program, like functions; whilst Hutter's optimisation is global. This causes an interesting problem: how do we switch to the optimised version? JITs don't bother switching calls which are already running; they just send any future calls to the optimised version. Whole-program optimisers can't do that, since there's nothing left to execute once the whole-program has finished. Exponential-restarting is an interesting hack to avoid this, but seems like a last-resort compared to local improvements.

I think it would be an interesting project to build an interpreter which works like Hutter Search, but allowing local improvements more like a normal JIT as well. It could keep track of a fixed number of search states (based on some longest-running/recently-used heuristic) to avoid having to always restart from scratch.

My guess is it would be pretty slow for "straightforward" tasks (assuming we don't bother to do much "manual" optimisation); long-running tasks with lots of iteration would see gradual speedups (as simple optimisations are found for their hottest loops); whilst a few very hard tasks, left running for a long time, may finish unexpectedly (when the optimiser stumbles across a much faster approach).

> This causes an interesting problem: how do we switch to the optimised version? JITs don't bother switching calls which are already running

Many JITs can do this. This is called "on-stack replacement" (OSR).

Ooo, didn't know about that, thanks :)

> An algorithm M is described that solves any well-defined problem p as quickly as the fastest algorithm computing a solution to p, save for a factor of 5 and low-order additive terms. M optimally distributes resources between the execution of provably correct p-solving programs and an enumeration of all proofs, including relevant proofs of program correctness and of time bounds on program runtimes. M avoids Blum's speed-up theorem by ignoring programs without correctness proof.

So this solves any problem that you can formally specify with the same complexity as the best algorithm?

This sounds too good to be true, what's the catch?

This prior discussion [1] on levin complexity might be relevant. I think the catch is basically that there's a huge constant out in front which makes this impractical. IIUC, in the case of levin search, the reason for this huge constant is that at a high-level that the algorithm functions as follows (for the specific case of solving 3-sat) for an input x of size n, enumerate all TMs 1..n and simulate each on x for a certain number of steps (fixed function of n). If any one of them produce a satisfying assignment, output that assignment.

You can see why this is a type of universal search: if the optimal algorithm is say polynomial (e.g. we assume that P=NP), then the above algorithm is also close to polynomial of one higher degree (as simulation is only a log factor) and by definition always outputs a satisfying assignment. The catch is that it only works if n is large enough to allow it to "discover" the right TM, and in the worst-case the minimum value of n for which the algorithm starts to work is the index of the encoding of a 3-sat algorithm, which is probably quite long. (A natural question to ask is that if such an TM index can be discovered, why not just use that TM directly? I believe it's because levin algorithm doesn't guarantee that the TM that we discover which produces a satisfying assignment is necessarily a valid TM for all inputs x. It could just be we got lucky and found a TM which worked only for this specific case.)

[1] https://news.ycombinator.com/item?id=27045091

M optimally distributes resources between the execution of provably correct p-solving programs and an enumeration of all proofs, including relevant proofs of program correctness and of time bounds on program runtimes

Reply on news.ycombinator.com