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²)), finding the height of the tree (O(log₂n)), sort data using merge sort(O(nlog₂n)), matrix multiplication O(n³) are few of the examples of P problems.
• An algorithm with O(2ⁿ) 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ⁿ)), Travelling salesman problem (O(n!)), Tower of Hanoi (O(2ⁿ – 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ⁿ))
• Travelling salesman problem (O(n!))
• Tower of Hanoi (O(2ⁿ – 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