[dpweb]

P and NP are classes of computational problems.

A problem in P can be solved in polynomial time - the computation required grows relatively slowly as the input size increases. Like sorting a list of numbers.

A problem in NP requires exponential time or greater, but a proposed solution can be verified quickly. For example, checking a completed Sudoku puzzle.

It is believed but unproven that all problems in NP are NOT in P.

[calfuris]

A problem in NP can have a (positive) solution verified in polynomial time. That's it. Requiring more than polynomial time to solve isn't part of the definition, and in fact it's an open question whether any problems in NP require more than polynomial time to solve.

Every single problem in P is in NP. What is believed but unproven is that some problems in NP are not in P.

[SoftTalker]

I have never really understood this, from the time it was first introduced to me in my undergraduate education nearly 40 years ago. It seems to boil down to saying "all unsolvable problems are not in the set of solvable problems" which seems like a tautology. I don't get why "P != NP" is considered so profound.

I feel like I have not yet found the proper explanation. Or I'm just too dense to get it.

[program_whiz]

Not sure you're wanting an explanation, but it comes down more to equivalent algorithms than rigid categories. For example there is a P algo to sort a list of numbers, but not to solve a sudoku (NP). However there is a polynomial algo to check sudoku (spaces ^ 2 if you check every space against every other space for rule violation).

However, the reason all NP algos are part of the same category is because you can solve any problem in NP by switching the problem into another problem in the same category and solving that. For example, you can turn sudoku into a graph coloring problem, which is also NP. You can turn sorting (P) into something like balancing a tree, which is also P.

The major question is "is there any algorithm that would allow us to change some NP problems into P problems, solve it, then use it for the original problem". E.g. could we take graph coloring and turn it into sorting a list of numbers?

So basically, if there is any way to bridge the two, then it might mean every NP problem is actually solvable by a P algorithm, under some transformation. This would be immense because it would completely change the way we solve those algorithms and greatly reduce compute costs.

While this seems far-fetched, realize that there are some problems that seem extremely expensive if done the naiive way, but are actually solvable in P. For example, you _could_ write an exponential sorting algo (try every element in every position), but clever people found a way to make it efficient (P). So its possible we just need the right algo to completely change the landscape of computing.

However, as you say, its almost self-evidently true that P != NP, but has never been proven so (to do so, we need to prove that no such algorithm can exist). But clearly, solving an exponentially complex problem using a O(log n) algo would be remarkable.

To take a concrete example, currently the best algos to exhaustively check a board game like chess or go are exponential (NP). Its easy to verify the winner, but its exponential to enumerate every possible move (e.g. 80^turns states). If we found a polynomial way to solve this (even by converting to something simplified), then it would mean we could exhaustively search chess polynomial to the number of moves (e.g. turns^100). This changes it from "cannot be done in the lifespan of universe" to "its possible with a powerful computer in measurable time". We already use heuristics and estimates to explore the exponential space in efficient time, so if we had a polynomial algo chess, markets, optimization, and other NP problems would be extremely efficient to solve.

[bjourne]

NP contains P. You're thinking of NP-hard problems.