Wednesday, August 18, 2010

P ≠ NP (part 2 correction)

In the previous post I said that one example of an NP problem is “Check if two computer programs always produce the same output.” jkff commented:
The "check if two computer programs always produce the same output" is not NP. It's simply undecidable and cannot be solved in any amount of time.
I blew it and oversimplified the statement. At Wikipedia, they have a list of commonly known NP-complete problems and on that list is “Inequivalence of simple functions.” I seriously mangled the meaning because I was daydreaming about assembly code. What I should have done is put some restrictions on what sort of computer program I meant.

First, we have to restrict ourselves to programs that we can prove will always return an answer within a given amount of time. A computer program that does not have any loops, backward jumps (gotos), subroutine calls, or exceptions should simply run from from start to finish. Second, we do not allow the program to save any state between runs; the output must be a pure function of the input. Furthermore, we restrict the input to a finite set (for example, integers that expressible in a single 32-bit word). Now suppose we have two such programs. To prove they are not equivalent, we need to find a 32-bit integer input that makes each program give a different answer. By trial and error we will eventually find such an input or exhaustively show that there is none. However, if someone were to claim that a particular input produced different output, then it is easy to check by simply trying it out.