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