P, NP, NP-Hard, NP-Complete

P: Problems that can be solved in polynomial time ex: testing if a number is prime.

NP : Problems that can be solved by non deterministic turing machine in polynomial time, or more simply the problems whose solutions can be verified in Polynomial time but cannot themselves be solved in polynomial time. ex: integer factoring. Easy to verify if 2 numbers multiply to a number.

NP-Hard: Take a problem and reduce it in polynomial time into another problem which can be solved (really fast) and the solution can be converted back to the solution of the original problem in polynomial time. This is of some importance as some problems in NP-Hard are themselves not actually NP! ex: TSP (given cities and their pairwise distances, find the shortest path that visits each city once and returns to its starting point.)

NP-Complete: Those problems that are in NP and also are NP-Hard are known as NP-Complete. ex: decision version of TSP (if there is a route shorter than length L).

If P=NP, it would imply that for every problem to which we can verify a solution in polyomial time, you can also solve it in polynomial time. This is neither proved nor disproved.




Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s