P vs NP - examples of P and NP
I'm currently studying 'p versus np'. Can someone help me in showing an example of a mathematical p problem and np problem?
A clear worked example would be much appreciated. Many thanks in advance.
$\endgroup$ 32 Answers
$\begingroup$First, all decision problems that are in P are also in NP. The interesting question of course is whether the reverse is also true: are NP and P in fact the same class, obscured only by the current lack of a clever algorithm to solve NP-complete problems in polynomial time.
An example of a decision problem in P is: Given a list of $n$ integers and an integer $k$, is there an integer in the list greater than $k$? Plainly the question can be answered in time linear to $n$ by stepping through the list and checking whether an integer is greater than $k$.
An example of a decision problem thought not to be in P, but still in NP is: Given a list of $n$ integers and an integer $k$, is there a set of integers within the list that when summed equal $k$? While this question is decidable, there is no known algorithm to decide it in (worst case) time that does not grow exponentially as $n$ grows. This is because there are an exponential number of sets to sum and check and our cleverest algorithms can only prune away a relatively small number of them.
$\endgroup$ $\begingroup$Arguably the most interesting problems in NP are the NP-complete problems because they are believed to be hard, i.e. not in P. Perhaps the most fundamental NP-complete problem is circuit satisfiability because that mimics a computer computation. The problem is to figure out if you can assign boolean inputs into a circuit to get a boolean logic formula satisfied. What makes this problem NP is that if there is a solution, then someone can show it to you and you can verify quickly (in polynomial time) that the solution works. However coming up with the solution seems like a hard problem.
$\endgroup$ 1
