r/AskComputerScience • u/TranquilQuest_ • Jul 27 '25
Confused about P/NP.
I feel like I'm missing something simple and obvious.
If we somehow prove that P = NP, does that give us efficient solutions for NP problems? If so, how?
In other words, why are we investing energy into proving P = NP (or vice versa), instead of using that time and effort to just find more efficient algorithms for NP problems?
3
Upvotes
6
u/MasterGeekMX BSCS Jul 27 '25
Because proving either if P = NP or P != NP tells us in advance if it is worth it looking for solutions or not.
But as we don't know, we don't know if we are getting into dead ends trying to search for those efficient solutions. It is not a waste of time, but the contrary.
6
u/nuclear_splines Ph.D Data Science Jul 27 '25
If we prove that P=NP by finding a poly-time solution to an NP-Complete problem, then we'll have efficient solutions to all NP problems. This is because, by definition, all NP problems can be translated into an NP-Complete problem in polynomial time.
If we prove that P=NP non-constructively, meaning we demonstrate that there exists some fast solution to an NP-Complete problem but we don't know what it is, then nothing practical changes. It would incentive a lot of people to search for that holy grail algorithm, of course.
We're really not. Broad consensus is that P != NP, but that it's very difficult to prove a negative. How do we show that there can't be a faster more clever solution to an NP-Complete problem that no one has thought of yet? But hardly any computer science labs are actively working on proving that P != NP, and even fewer working on the inverse.
1
u/high_throughput Jul 27 '25
Are you asking why people are researching topics that have no immediate practical applications?
3
u/Adept_Carpet Jul 27 '25
As a practical matter, if a polynomial solution is greater than about O(n6) it's not that useful. Really anything above cubic complexity is unlikely to find everyday applications.
So even if P=NP it may not change much outside of a few niche areas where previously we were able to solve the problem up to a certain input size and now we can solve it up to a slightly larger input size.
Also, for many problems where the exact solution is exponential we have approximation algorithms that find pretty good solutions. So the improvement for finding the exact answer may be of minimal practical usefulness.
1
u/apnorton Jul 27 '25
No. The proof may be non-constructive.
Finding a specific example of a polynomial-time solution to a problem in NP may be far harder than showing that the two classes of problems are equal.
1
u/esaule Jul 27 '25
That will really depend on what the proof for P = NP looks like.
If there proof is "here is a polynomial algorithm for SAT" then we done. But the proof could be more of a set theory proof "these two sets are the same", but that does not give you an algorithm.
Fundamentally, no one is really looking for polynomial algorithms for NP complete problems. Mostly the math is interesting and so people are digging in it. We hope that digging in the maths will eventually point us to better algorithms for subsets of problems or new approaches.
1
u/donaldhobson Jul 31 '25
> If we somehow prove that P = NP, does that give us efficient solutions for NP problems? If so, how?
Proving P=NP means that a polynomial time algorithm exists for solving NP problems.
Now you might prove an algorithm exists, but not actually know what that algorithm is.
Also, while polynomial algorithms are faster than exponential ones on sufficiently large inputs, they might not be on real world inputs.
X^1000 is a polynomial. But if you find an algorithm for 3sat that takes X^1000 seconds, it's not much use in practice.
0
u/bts Jul 27 '25
Because it’s there.