A simple definition of P and NP (Entry Nr. 1069, by user 1 | edit) |
|
|
There has been a lot of talk lately on what is considered to be the greatest unsolved problem of computer science: The question if "P=NP". Since even the wikipedia page is so mindblowing that I have a hard time understanding it, I spend some time today trying to come up with a simpler definition. Here it is.
My attempt to explain P and NP:
P is the class of questions that a turing machine can answer in n^x steps. Where n is the length of the input and x is a problem specific number.
NP is the class of questions where a turing machine can decide if a given solution is correct in n^x steps. Where n is the length of the input and x is a problem specific number.
The famous question "Is N=NP" then comes down to "If a turing machine can verify an answer to a question in n^x steps, can it also FIND a solution in n^x steps?". It generally believed that this is not the case and that there are questions that need x^n steps to answer, even if any answer can be verified in n^x steps.
Im not sure if this is correct. Some people with math background looked over it and general census seems to be that it is ok. |
|
|
Create a new entry at this position
|
|
|
