A simple definition of P and NP

gibney.org : Math : 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:
 
 <div style="background: #fffff0; border: 1px solid #e0e0e0; padding: 0.5em">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.</div>
 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