7 ms·
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 instincti
by aeneasmackenzie 2y ago
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.
- deleted 2y ago[deleted]
- gowld 2y agoIf 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?
- mathgradthrow 2y agoWe 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.
- gowld 2y agoMy point is that N is most probably bigger than the entire Universe, if it turns out to be finite.