Timeline for $\mathbf{P} = \mathbf{NP}$, what's the problem?
Current License: CC BY-SA 4.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 13, 2022 at 15:20 | comment | added | AnoE | Fair enough, @DanRomik. Guess we'll leave it up to Noam whether he wants to flesh it out. :) | |
| Apr 13, 2022 at 14:32 | comment | added | Dan Romik | @AnoE sure, it’s a good answer and I upvoted it. I just thought we should be clear about the limits of our knowledge, so that people who might be inclined to think about this integral approach further don’t assume at the outset the idea is completely impossible and get scared away. Call it “informed consent”. Even if the approach doesn’t lead to a proof that P=NP (it most probably won’t) there may well be some useful insights to be gained from thinking about it. | |
| Apr 13, 2022 at 13:22 | comment | added | AnoE | @DanRomik, in principle yes. But OP is asking why his approach does not just "simply" solve P=?=NP once and for all, assuming/implying his approach is solvable polynomial time, even if only as an approximation. This answer shows - on an equally rough level of detail to the answer - the "exponentiality" aspect contained in OP's algorithm. Seems a pretty OK answer to me. At this point, one would have to come up with a way to make OP's algo polynomial with the added info from this answer; that the answer has details left open seems inconsequential to me. | |
| Apr 13, 2022 at 8:42 | comment | added | mlk | @StevenStadnicki There may be another good point in there. Having only a trustable answer may not good enough. To show that P=NP you need a polynomial time algorithm that always works, not one that works 99,99999% of the time. The latter would only show NP $\subset$ BPP (which would be a big result in itself though). | |
| Apr 13, 2022 at 2:13 | comment | added | Dan Romik | This is good as a heuristic explanation of why OP’s approach isn’t likely to work. But perhaps we should make clear that there’s no a priori guarantee that someone couldn’t find some ingenious way of approximating the integral in polynomial time. In other words, this approach is no less viable as a way of proving P=NP (for someone who believes that’s not an utter waste of time) than the more direct combinatorial approach, for which there is an equally convincing heuristic explanation of why it’s unlikely to work. | |
| Apr 13, 2022 at 1:37 | comment | added | Steven Stadnicki | For instance (to use OP's suggestion), to get sufficient resolution for Monte Carlo integration to return a 'trustable' value we would have to sample roughly $\Omega(\sum_i 2^{A_i})$ points because of the Nyquist sampling theorem. | |
| Apr 12, 2022 at 22:44 | history | answered | Noam D. Elkies | CC BY-SA 4.0 |