P/NP?

Back to another Millennium Prize problem!

There are two types of questions: one, where an algorithm can solve the question in polynomial time (P), and ones, where there is no way to find the answer quickly, but if information is given on showing what the answer is, it can be quickly verified, which is NP, or nondeterministic polynomial time.

The question, stated by Wikipedia, is “if the solution to a problem is easy to check for correctness, must the problem be easy to solve?” or in other words, is P = NP?

If P ≠ NP, then both P questions and NP-complete questions are within the class of NP questions. NP-complete questions are a set of problems where to each of which any other NP-problem can be reduced in polynomial time and the solution can be verified in polynomial time as well. NP problems, therefore, can transform into any NP-complete problems.

Now, if you want, go visit the Wikipedia page on it to understand better about P vs NP.

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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s