P and NP Problems
P and NP Problems are the class of problems. Problems are grouped based on their complexity.
- 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!))
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