We have very different beliefs about P != NP. I would be willing to make the following wager, if it could be suitably enforced with sufficiently low overhead. If a proof that P != NP reaches general acceptance, you will pay me $10000 with probability 1/1000000 (expectation $.01). If an algorithm provably solves 3SAT on n variables in time O(n^4) or less, I will pay you $1000000.
We may need to adjust the terms. The most worrisome parts of that bet are twofold: 1) I don’t have 10^5 dollars, so on my end, paying $1000 with probability 1/100000 which has the same expectation probably makes more sense. 2) I’m not willing to agree to that O(n^4) simply because there are many problems which are in P where our best algorithm known is much worse than that. For example, the AKS primality test is O(n^6) and deterministic Miller Rabin might be O(n^4) but only if one makes strong assumptions corresponding to a generalized Riemann hypothesis.
Perhaps it was not clear what I meant by an individual going FOOM, which is fair since it was a bit of a misuse. I mean just that an individual with access to such an algorithm could quickly amplify their own power and then exert a dominant influence on human society. I don’t imagine a human will physically alter themselves. It might be entertaining to develop and write up a plan of attack for this contingency.
Not necessarily. While such an algoirthm would be useful many of the more effective uses would only last as long as one kept quiet that one had such a fast SAT solver. So to take full advantage requires some subtlety.
. I think the step I assume is possible that you don’t is the use of a SAT solver to search for a compact program whose behavior satisfies some desired property, which can be used to better leverage your SAT solver.
There’s a limit to how much you can do with this since general questions about properties of algorithms are still strongly not decidable.
We may need to adjust the terms. The most worrisome parts of that bet are twofold: 1) I don’t have 10^5 dollars, so on my end, paying $1000 with probability 1/100000 which has the same expectation probably makes more sense. 2) I’m not willing to agree to that O(n^4) simply because there are many problems which are in P where our best algorithm known is much worse than that. For example, the AKS primality test is O(n^6) and deterministic Miller Rabin might be O(n^4) but only if one makes strong assumptions corresponding to a generalized Riemann hypothesis.
Not necessarily. While such an algoirthm would be useful many of the more effective uses would only last as long as one kept quiet that one had such a fast SAT solver. So to take full advantage requires some subtlety.
There’s a limit to how much you can do with this since general questions about properties of algorithms are still strongly not decidable.