Hacker News Reader

Comment by fragsworth | Hacker News Reader

Suppose we have a human-written program that's N-bits long. It takes an input, and generates an infinite output by performing some hashing of the input. We run it on an M-bit input to get some output, then stop it manually.

Now suppose we have an input and the output made by this program. But we don't have the program. Suppose we want to discover by brute force what the program was.

The brute-force algorithm will create every possible program up to N bits long, and run each one until either a difference in outputs is found, or it found the correct output, or too much time has passed.

How do you come up with the order-notation for this brute-force algorithm?

View on HN

Since you're bounding (with a constant) the time each iteration can take, this is just O(2^n).

EDIT: I suppose if the time bound per program is a parameter "m" that you can vary, then it's actually O(m*2^n).

Without the bound, this algorithm is unlikely to work, since programs can run indefinitely.

If you modify your algorithm to only generate programs without any infinite loops, you've solved the halting problem, which is impossible.

>If you modify your algorithm to only generate programs without any infinite loops, you've solved the halting problem, which is impossible.

Nonsense, there is no reason you cannot design an algorithm that uses a halting oracle. Running that algorithm may be difficult though.

I'm sure you know this, but I'd just like to clarify something:

You absolutely can generate only programs that terminate; for instance, throw out any that have recursion or unbounded loops, or use a non Turing complete language that is guaranteed to terminate.

That you can't solve the halting problem in general does not mean that static analysis is fruitless. The answer to "does this terminate" will be yes, no or maybe, almost always in the latter category.

The correct thing to say would be:

If you modify your algorithm to only generate programs without infinite loops, you've most likely thrown out the correct solution.

I'm confused. Why is the output infinite? Do we know when the hashing was stopped?

I'm not sure this is a decidable problem with just the information you gave.

Did you just make up the problem, or is that inspired from a real world situation?

The "too much time has passed" bound on each iteration guarantees that you don't end up running an iteration forever, and makes the algorithm O(2^N), since the number of programs up to N bits long is 2^(N+1) - 1.

In a tangential note, if P=NP, a sufficiently carefully crafted algorithm very much like that suffices to solve any NP complete problem in polynomial time! (Of course the constants are ridiculously, absurdly large)

http://lucatrevisan.wordpress.com/2010/03/07/on-the-necessit...

O(2^n) where n is the number of bits?

Reply on news.ycombinator.com