just a logo :)

search:


See as: raw | code

terms of service | imprint

gibney.org
is powered by m1d1





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