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. |