# P and NP Problems

P and NP Problems are the class of problems. Problems are grouped based on their complexity.

## P-class Problems

• P problems are a set of problems that can be solved in polynomial time by deterministic algorithms.
• P is also known as PTIME or DTIME complexity class.
• P problems are a set of all decision problems which can be solved in polynomial time using the deterministic Turing machine.
• They are simple to solve, easy to verify and take computationally acceptable time for solving any instance of the problem. Such problems are also known as “tractable”.
• In the worst case, searching an element from the list of size n takes n comparisons. The number of comparisons increases linearly with respect to the input size. So linear search is P problem.
• In practice, most of the problems are P problems. Searching an element in the array (O(n)), inserting an element at the end of a linked list (O(n)), sorting data using selection sort(O(n2)), finding the height of the tree (O(log2n)), sort data using merge sort(O(nlog2n)), matrix multiplication O(n3) are few of the examples of P problems.
• An algorithm with O(2n) complexity takes double the time if it is tested on a problem of size (n + 1). Such problems do not belong to class P.
• It excludes all the problems which cannot be solved in polynomial time. The knapsack problem using the brute force approach cannot be solved in polynomial time. Hence, it is not a P problem.
• There exist many important problems whose solution is not found in polynomial time so far, nor it has been proved that such a solution does not exist. TSP, Graph colouring, partition problem, knapsack etc. are examples of such classes.

### Examples of P Problems:

• Insertion sort
• Merge sort
• Linear search
• Matrix multiplication
• Finding minimum and maximum elements from the array

## NP-Class of Problems

• NP is a set of problems which can be solved in nondeterministic polynomial time. NP does not mean non-polynomial, it stands for Non-Deterministic Polynomial-time.
• The non-deterministic algorithm operates in two stages.
• Nondeterministic (guessing) stage: For input instance I, some solution string S is generated, which can be thought of as a candidate solution.
• Deterministic (verification) stage: I and S are given as input to the deterministic algorithm, which returns “Yes” if S is a solution for input instance I.
• The solution to NP problems cannot be obtained in polynomial time, but given the solution, it can be verified in polynomial time.
• NP includes all problems of P, i.e. P ⊆ NP.
• Knapsack problem (O(2n)), Travelling salesman problem (O(n!)), Tower of Hanoi (O(2n – 1)), Hamiltonian cycle (O(n!)) are examples of NP problems.
• NP Problems are further classified into NP-complete and NP-hard categories.
• The following shows the taxonomy of complexity classes.
• The NP-hard problems are the hardest problem. NP-complete problems are NP-hard, but the converse is not true.
• If NP-hard problems can be solved in polynomial time, then so is NP-complete.

### Examples of NP problems

• Knapsack problem (O(2n))
• Travelling salesman problem (O(n!))
• Tower of Hanoi (O(2n – 1))
• Hamiltonian cycle (O(n!))