7 Difference Between P And NP Problems In Computer Science

SHARE

What Are P And NP Problem?

Computer algorithms take a certain amount of time to solve the problem they are tasked with. Generally, you can roughly estimate how much time an algorithm will take using the number of elements they need to handle. Computer scientists call the number of elements N.

Because some algorithms are more or less efficient than others, the time they take to complete could be related to NN2N3, and so on. The important thing, though, is that the exponent is a constant—it’s 1, or 2, etc. When this is the case, an algorithm is said to complete in polynomial time, or P.

Unfortunately, not all problems work this way. Solving some problems can take an algorithm an amount of time proportional to 2N, 3N, and so on. In this case, N is the exponent, meaning that every element the algorithm has to deal with increases its complexity exponentially. In this case, the algorithm can be completed in exponential time, or NP (which really stands for nondeterministic polynomial time).

The difference between these two can be huge. If a P algorithm has 100 elements, and its time to complete working is proportional to N3, then it will solve its problem in about 3 hours. If it’s an NP algorithm, however, and its completion time is proportional to 2N, then it will take roughly 300 quintillion years.

Therefore, A problem is called NP if its solution can be guessed and verified in polynomial time, and nondeterministic means that no particular rule is followed to make the guess. On the other hand, a P problem is one that can be solved in polynomial time by deterministic algorithms.

• P problems are set of problems which can be solved in polynomial time by deterministic algorithms.
• The problem belongs to class P if it’s easy to find a solution for the problem.
• P Problems can be solved and verified in polynomial time.
• P problems are subset of NP problems.
• It is not known whether P=NP. However, many problems are known in NP with the property that if they belong to P, then it can be proved that P=NP.
• All P problems are deterministic in nature.
• Example: Selection sort, linear search