Hacker News Reader

And in the P=?NP case Aaronson uses, the answer wouldn't be "P=NP" (a classical answer -- totally useless) but the actual function NP->P.

People just instinctively know that you need to know which side of the disjunction you're on, and they haven't been trained in classical logic to forget it.

View on HN

If NP somehow was proved to be P, with a likely value being something like O(n^(10^10^10)) or much larger, would the actual constructive reduction be at all useful?

We already have such a machine. If P=NP then there is some Turing machine that produces, for instance, a 3-SAT certificate in polynomial time.

We may enumerate the turing machines and call ours the M-th one. Given a boolean expression P, increment a counter N and run the first N turing machines on P for N steps, check each of the outputs of these against the certificate checker.

If M runs in time O(|P|^n) and the certificate checker is O(|C|^m) and then our hybrid machine runs in something like O((M+|P|^n)^2m).

All we're missing is a proof.

My point is that N is most probably bigger than the entire Universe, if it turns out to be finite.

Reply on news.ycombinator.com