**P and NP Problems**

P and NP Problems is the important topic of the Analysis & Design of Algorithm. Moreover, freestudy9 has all kind of important information and topic related to it.

**P 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
for some constant*O*(*n*^{k})*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 Problems **

- <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(2
^{n/2}) - Travelling salesperson problem (O(n
^{2}2^{n})). - Graph coloring problem.
- Hamiltonian circuit problems, etc…

- Knapsack problem O(2

**Related Terms**

ADA Algorithms, String Matching with Finite Automata, Knuth Morris Pratt Algorithm, Rabin-Karp Algorithm

## Leave a Reply