P,NP,NP Hard and NP Complete

P, NP, NP Hard and NP Complete

 

These refer to how long it will take a program to run.

 

P

 

Programs that can run in polynomial time are in class P.For example, if you have an algorithm that finds a smallest integer in array, it takes linear time to solve this. There can also be some quadratic or exponential time algorithms. If the running time is some polynomial function of the size of the input, then we say that algorithm runs in polynomial time and problem it solves is in class P.

 

NP

 

Now, there are a lot of problems that don't run in polynomial time on normal computer but run can run in polynomial time on nondeterministic turing machine. A turing machine can do all the work that regular computer can do. Hence, all problems in P are also in NP. If we can verify the solution to a problem in polynomial time, then we say that those problems are in NP.

Some people think P = NP, which means any problem that can be verified in polynomial time can also be solved in polynomial time and vice versa. If they could prove this, it would mean that people would be able to construct faster algorithms for a lot of important problems.

 

NP-Hard

 

A lot of times we can solve a problem by reducing it to a different problem. We can reduce problem B to problem A, if given a solution to problem A, we can easilty construct the solution to problem B. If a problem is NP hard, I can reduce any problem to that problem. So, if I can solve that problem, I can easily solve any problem in NP.

 

NP Complete

 

A problem is NP Complete if problem is both:

1)NP Hard and

2)NP

 

Complexity classes are one way to talk about how difficult or easy a problem is. Complexity theory can get very technical but the basics are actually intuitive, and it's possible to understand the P versus NP issue with very little math background.

Contributor's Info

Created:
0Comment