Timeline for Is there a challenge with which one could reasonably show to have found a feasible polynomial algorithm for an NP problem?
Current License: CC BY-SA 4.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 7 at 6:37 | answer | added | NooneAtAll3 | timeline score: 1 | |
| Sep 27, 2023 at 21:45 | answer | added | Bernardo Subercaseaux | timeline score: 3 | |
| Sep 27, 2023 at 8:31 | comment | added | Command Master | If you can find, in a bunch of previously unbroken hash functions, with independent mechanisms, a preimage to some meaningful hash string, then I believe most people will find that extremely strong evidence you have proven the non-existence of one-way functions, and perhaps even P=NP. | |
| Sep 27, 2023 at 8:27 | comment | added | Command Master | @YvesDaoust I don't think you are addressing the relevant point, which I understood as "suppose one has a practical algorithm for an NP-complete problem, can he prove that without revealing the algorithm?" | |
| Sep 26, 2023 at 7:40 | comment | added | user16034 | "give strong evidence" is not enough and probably unrealistic. Non-polynomial behavior is understood "in the worst-case" and we don't know intrinsically worst-case problems. An informal but correct proof could do. By the way, we already have very strong evidence that the conjecture holds. | |
| Sep 26, 2023 at 7:38 | comment | added | user16034 | If you truly have broken the conjecture, spend the next year learning relevant proof techniques and win the gold watch. | |
| Sep 26, 2023 at 7:33 | comment | added | user16034 | "No huge constant" is irrelevant. What matters is the asymptotic behavior. | |
| S Sep 25, 2023 at 22:01 | review | First questions | |||
| Oct 9, 2023 at 22:03 | |||||
| S Sep 25, 2023 at 22:01 | history | asked | tistorm | CC BY-SA 4.0 |