- In computational complexity– a subfield of theoretical computer science and mathematics, the question of whether all so-called NP problems are P problems.
- P is a set of relatively easy problems, and NP is a set that includes what seem to be very, very hard problems, so P = NP would imply that the hard problems have relatively easy solutions. But the details are more complicated.
- It is called the most important outstanding question in theoretical computer science; the equivalency of P and NP is one of the seven problems that the Clay Mathematics Institute will give you a million dollars for proving — or disproving.
- A P problem can be solved in “polynomial time,” which means that an algorithm exists for its solution such that the number of steps in the algorithm is bounded by a polynomial function. Thus, P problems are said to be easy, or tractable.
- 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.
- The barrier that the P vs NP problem stands for encompasses every field where the solution to a problem is blocked by the availability of significant computational resources.
- So, these fields include logistics, finance, and even climate modelling, all of which could experience paradigm shifts if the P vs NP problem is solved in favour of the P = NP outcome.
Dig Deeper: Read about Semiconductors and their working
