0

P, NP, NP-C, NP- Hard

What is P, NP, NP-C, NP-Hard ???

When I was in college this was the toughest topic to digest, at least for me. In general a lot of students find difficult to understand what this is about.

Alright lets talk about it,
In the world of computer science not every problem is solvable, even if you have unlimited time and current supercomputers to run your program. For example Travelling salesman problem (TSP)

Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?”

As the number of cities increase number of combinations increase, and makes it impossible for modern day computers to compute shortest path in acceptable time. Even 100 cities will have (100-1)!/2 which is a lotttt !!!.

P : P means problems that can be solved in polynomial time. Example Linear search takes just O(n) or Binary search which takes O(log n), are an examples of P problem.

NP : Non Deterministic Polynomial. Is a set of DECISION problems, for which there is a non deterministic algorithm that runs in polynomial time.

NP-C : NP- Complete are a set of problems that satisfy following,
Let’s say problem A is NP-Complete.
1) A is NP
2) And All NP problems can be polynomially reducible to A.

NP-Hard : NP-Hard problems follow above criteria, but its not necessary to be in NP for a problem to be called NP-Hard. So problem A is NP hard if

1) All NP problems are polynomially reducible to A.

Diagram From Wikipedia :

We dont know P=NP or P!=NP yet.
If you prove either there is a million dollar award for it. 🙂

What is Polynomial Reduction mean ?
When I say problem B is Polynomially reducible to A, means that we can convert problem B somehow (Do some processing on input for B) such that it becomes problem A. So we reduce problem B to problem A in polynomial time.

So now if I can solve problem A in polynomial time then I can solve B in Polynomial time. Why ?
You can convert B -> A in Polynomial time so B is as good as solving A and you know A can be solved in polynomial time. So total time required is Conversion of B-> A (Poly Time) + solving A (Poly Time) = Polynomial Time.

To express in code ,

We know A can be solved in polynomial time. Assume method SolveA(input); //solves problem A in P time.
Assume T ConvertBtoAInP(); // converts problem B to A.

So the method SolveB() will look like

SolveB()
{
SolveA(ConverBtoAInP());
}

Let me know if you have any questions.


Warning: count(): Parameter must be an array or an object that implements Countable in /home/algotu5/public_html/wp-includes/class-wp-comment-query.php on line 405