 search:

imprint

 A simple definition of P and NPEntry Nr. 1069, by user 1 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.