Introduction to P, NP, NP hard, NP Complete

In this tutorial we shall learn about what is P, NP, NP hard, NP Complete problems.

This is a complex topic. I have tried my best to make you understand in a easy way.

First, full form of P and NP.

P -> Polynomial Time

NO -> Non deterministic Polynomial Time.

Before we understand polynomial time, let’s understand constant time and linear time.

Any algorithm is said to take Constant time, if we are able to get the value by doing single operation irrespective of input size. It is written as O(1).

1. Accessing element in an array will always take a constant time irrespective of input size.

2. If the array is sorted in ascending order, getting the min element is always done in constant time.

Linear time: Any algorithm is said to take linear time if the time complexity is O(n). It means, the time consumed will be increased as input size increases.

Example;

1. Accessing min element in an unsorted array. If the min element is at the end of the array, it will take O(n) time. And the time will increase as the input size is increased.

Now, Polynomial Time:

An algorithm is said to take polynomial time, if the upper bound of a polynomial expression is O(n^k) where k is a constant.

Ideally, linear time is a polynomial time where K = 1. Below are some of the algorithms that can be solved in polynomial time.

Linear Search O(n)

Insertion Sort O(n^2)

The above problem can be solved at deterministic polynomial time.

Below are some of the algorithms that can be solved in exponential time:

Travelling Salesman Problem O(2^n)

Hamiltonian Cycle O(2^n)

0/1 knapsack Problem O(2^n)

The above problem cannot be solved in deterministic time. Hence we try to solve it through non deterministic time.

An algorithm, where the steps are clearly defined is called as deterministic algorithm.

Example: Bubble sort, quick sort, Linear search.

The algorithms that shows different behaviour for same input, are called as non-deterministic algorithms.

All deterministic algorithm can be solved in polynomial time, but non deterministic algorithms cannot be solved in polynomial time.

Before going to our main topic, let’s understand one more concept.

These are the problems that can be solved with a series of “yes” or “no” based decisions. This kind of problems are known as decision based problems. There might be other kind of problems, but we shall stick to decision based problem for now, so to understand next topic.

Now coming to our main topic:

P, NP, NP hard, NP Complete

For these kind of problem, there are efficient algorithms that are designed to solve in polynomial time at the worst case.

So P is a class of decision based problems that can be solved efficiently.

For NP class problems, we don’t know how to solve them efficiently. But we try to verify the answer efficiently thus having a proof.

So NP is a class of decision based problems, that can be verified efficiently. It means that there is an algorithm present that can verify the output of the problem.

So P class problems, that can be efficiently solvable.

NP class problems, that can be efficiently verifiable.

So most of the time, we hear that P = NP, if and only if, the problem in class P are efficiently verifiable.

Before going to learn about NP hard and NP complete, we have to understand what is reduction based problem?

If you have a problem “M”, it can be reduced to another problem “N” and that “N” problem can be efficiently solved. These kind of problems are called as reduction based problems.

Properties of Reduction based problem:

1. If A is reducible to B in polynomial time, then A can be solved in polynomial time.

2. If A is not solved in polynomial time, then it means, B also cannot be solved in polynomial time.

A problem is called as NP hard, if all the problems in NP can be reduced to polynomial time. It means if I have a set of problems in P and NP, and they can be reduced in polynomial time, then those set of problems are called as NP based problems.

The group of problems what are both NP and NP hard is called as NP Complete Problems.

The intersection of NP and NP hard set of problems are called as NP complete.