# 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(n
^{2})), finding the height of the tree (O(log_{2}n)), sort data using merge sort(O(nlog_{2}n)), matrix multiplication O(n^{3}) are few of the examples of P problems. - An algorithm with O(2
^{n}) 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(2
^{n})), Travelling salesman problem (O(n!)), Tower of Hanoi (O(2^{n}– 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(2
^{n})) - Travelling salesman problem (O(n!))
- Tower of Hanoi (O(2
^{n}– 1)) - Hamiltonian cycle (O(n!))

## P and NP Problems – Differentiate

Sr. No. | P Problems | NP Problems |

1. | P problems are set of problems which can be solved in polynomial time by deterministic algorithms. | NP problems are problems which can be solved in nondeterministic polynomial time. |

2. | P Problems can be solved and verified in polynomial time | The solution to NP problems cannot be obtained in polynomial time, but if the solution is given, it can be verified in polynomial time. |

3. | P problems are a subset of NP problems | NP Problems are a superset of P problems |

4. | All P problems are deterministic in nature | All the NP problems are non-deterministic in nature |

5. | Example: Selection sort, Linear search | Example: TSP, Knapsack problem |

Youtube Channel: https://shorturl.at/inryW