P and NP Problems
- The class P consists of those problems that are solvable in polynomial time. More specifically, they are problems that can be solved in time O(nk) for some constant k, where n is the size of the input to the problem.
Fundamental complexity classes.
- The class of problems that can solve in polynomial time called P class.
- Also, These are basically tractable. Few examples of P class problems are,
- A set of decision problems with yes/no answer.
- Calculating the greatest common divisor.
- Sorting of n numbers in ascending or descending order.
- Searching for an element from the list, etc.
- <NP = Non-Deterministic polynomial time
- NP means verifiable in polynomial time
- The class NP consists of those problems that are “verifiable” in polynomial time.
- Also, What we mean here is that if we were somehow given a “certificate” of a solution, then we could verify that the certificate correct in time polynomial in the size of the input to the problem.
- NP one of the most fundamental classes of problems in computational complexity theory.
- The abbreviation NP refers to non-deterministic polynomial time.
- Moreover, These problems can solve in non-deterministic polynomial time.
- For example
- Knapsack problem O(2n/2)
- Travelling salesperson problem (O(n22n)).
- Graph coloring problem.
- Hamiltonian circuit problems, etc…