17 Dec
2003
17 Dec
'03
11:17 p.m.
question struck me: If a Grand Unified Theory exists, would it not prove P=NP to be true? No. Hardly. behaviour we believe to be non-deterministic really isn't: it obeys the GUL. So P=NP must be true, since NP is an artifact our pre-GUL way of looking at things. Non-determinism will exist forever as an idea, just the same way that no real number has ever been measured, merely approximations to them. NP is an expression of that idea. There are other ways to formalize NP without resorting to non-determinism. NP is the class of problems for which there exists a witness to a PTIME computation. Non-determinism is only another way of rephrasing the existential quantification. Eric