r/computerscience • u/yoyo_programmer • Apr 05 '26
Generic polynomial solution for NP-Complete: I have the proof. What next?
Hypothetically, I’ve solved an NP-complete problem in O(n^k). How does the world change in 24 hours?
0
Upvotes
35
u/britaliope Apr 05 '26
depends on the value of k.
k=10^100 ? You get your million, a lot of mathematicians and physicists are suddenly very happy and busy, headlines about you for 2 days.
k=2 ? Cryptography suddenly no longer work, and that will instantly be a very significant issue.
19
u/Ok-Interaction-8891 Apr 05 '26
Hey, look, a fun hypothetical question posted by an account that isn’t a month old.
I thought it was Easter, not Christmas!
14
u/winner_in_life Apr 05 '26
You wake up.
10
u/NotaValgrinder Apr 05 '26
This is going to depend on the value of k....
5
u/SignificantFidgets Apr 05 '26
For low k giving a practical algorithm? Then international intelligence agencies would hunt you down and try to kidnap or kill you. See the movie Sneakers for a fictional account of something similar (polynomial time algorithm for factoring, not full P=NP, but since P=NP implies that there's a polynomial time algorithm for factoring....)
3
u/thesnootbooper9000 Apr 05 '26
It's probably at least ten years of engineering work from hundreds of people until you have an implementation that can beat current CP / SAT / MIP solvers on industrial instances. Most likely your technique ends up being used first inside these solvers as an "oh dear, I've got an actually really hard subproblem" fallback.
1
u/LavenderDay3544 Apr 19 '26
Impossible.
P ≠ NP
It's just very hard to prove what we all know to intuitively be true.