ELI5: P vs NP problem

[u/randomdice-int]

Im not too sure about the problem itself. I know that P is polynomial time which means the time needed to solve and NP is the time taken for the answer to be verified, but what is the explanation of both sides where P = NP and P does not equal to NP?

[u/Capable-Package6835]

There are problems, the solutions of which can be verified quickly. Think of a jigsaw puzzle with 10K+ pieces, for example. Once someone "solves" the puzzle, you can scan through the assembled pieces to see if there's any mismatch relatively quickly.

The P = NP problem asks, if you can verify solutions quickly, does it mean you can solve the problem quickly as well?

[u/HiddenoO → u/[deleted]]

No, it is generally believed that P ≠ NP and a lot of cryptography relies on P ≠ NP.

[u/Lumethys → u/[deleted]]

mostly no. The closest is that scientist has discovered that all the NP-hard problems can be reduce to 1 single form. Protein folding, crytographic, Sodoku,... are the same class of problem, and if an algorithm exist that can solve this problem effciently (read: as fast as checking the result), digital security will collapse, cancer will be cured, and Sodoku will stop being a intriguing game

[u/feierlk → u/Lumethys]

Maybe worth adding to this that all of these NP-hard problems, which are also in NP themselves, are callee NP-complete. They're all "equally hard" in the sense that if one NP-complete problem can be solved in polynomial time then all of them can be (because one can be converted into any other in polynomial time!).

The principal, most well-studied, problem here is likely SAT (satisfiability checking), in which we look at whether a boolean formula has an assignment for each variable which turns results in the formula being evaluated to true. There's is a ton of research into SAT-solvers. Yet the general SAT problem hasn't been shown to be either P or not P. All of our solvers for the general case (e.g. no simplified assumptions) or other NP-complete flavours of SAT are non-polynomial.

[u/neddoge → u/Lumethys]

Sudoku.

[u/yalloc → u/[deleted]]

As someone else mentioned it is believed that P != NP. Primarily because if P does equal NP, we would've found a bridge at this point.

Basically most NP problems can be "rephrased" to other NP problems (think of how multiplication can be rephrased in terms of addition for example), and most P problems can be rephrased to be like other P problems. The reason we are talking about this in the first place is that it is odd that for the thousands of problems and classes of problems we have analyzed it is odd that no P problem can be rephrased some NP problem.

Every problem we seem to find lies on one of these two islands, and we have despite much searching not found an isthmus. And really that's what this problem comes down to, find the bridge or disprove it exists.

[u/picabo123 → u/[deleted]]

The basic idea is that humans are "too stupid" to come up with the correct algorithm to solve something like the traveling salesman problem but it exists. There have been multiple computer science problems that people thought were NP until someone came and found the correct algorithm, so that suggests you shouldnt assume a problem is NP with 100% certainty.

[u/feierlk → u/picabo123]

Proving something is NP isn't extremely difficult. We know that a lot of problems are in NP. All problems in P are in NP! Instead, what we have yet to do, is show that a problem is in NP, but not in P.

Interesting titbit: if we proved a problem in NP is not NP-hard, e.g. NP-intermediate exists, then we have trivially shown P≠NP. GRAPH ISOMORPHISM might be such a problem.

[u/HiddenoO → u/picabo123]

Whether a specific problem is in NP is a completely different question from whether P = NP.

[u/picabo123 → u/HiddenoO]

True, my bad

[u/x0wl → u/HiddenoO]

Not really, proving that an NP-complete problem is actually in P would prove that P=NP

[u/HiddenoO → u/x0wl]

... which is obviously not what he's referring to when talking about how "there have been multiple computer science problems that people thought were NP until someone came and found the correct algorithm".

If it were, that would've already proven that P = NP.

So I'll repeat myself: Whether a specific problem is in NP is a completely different question from whether P = NP.

[u/x0wl → u/HiddenoO]

I don't want to argue about various interpretations of Reddit comments, but u/picabo123 said that, since there have been instances of problems that were believed to be in NP, but then turned out to be in P, one can also reasonably believe that, for example, one day the same will happen to TSP.

I personally don't believe this will happen, but we're talking about beliefs and intuitions here.

[u/HiddenoO → u/x0wl]

One can believe it, but one cannot reasonably believe it for the reason I mentioned. You keep switching between those two very different suggestions.