Following a definition given by reddit:
Okay, so basically it’s looking at two things:
P is a problem that can be solved really easily by a computer.
NP is a problem that you can check for correctness very easily once solved.
For example, NP is like a Sudoko puzzle: once you complete it, it’s very fast to check and make sure you’ve solved it, but it takes a lot of time to solve it.
The P vs NP problem/question is basically asking, are these two problems the same?
Maybe trying another way: is there an algorithm, or a formula, or an equation that will let a computer program quickly solve any problem that can be easily checked? Not a universal equation, but one for different problems.
What i don't get it is why verification is relevant, see, isn't verification just a independent problem with no relation to the original problem? since you have different parameters and different objectives? if verification is not related to the original problem does the question still makes sense?
Another thing that comes to my mind is classification of problems in general, do we have proofs that a single problem can be P exclusive? like there is no method in NP that can solve this problem? because seems hard to proof too, exactly like the people who say that you cant prove NP != P because you need to check for all P solutions.
[link] [comments]












English (US) ·