The P vs. NP Question

 

 

The P vs. NP Question

Is finding solutions no harder than checking them? Can the ability to find good solutions (“creativity”) become as routine as the ability to appreciate good solutions?

Summary

P is the class of problems for which solutions can be found efficiently (in time that is polynomial in the length of problem description). NP is the class of problems for which solutions can be checked in polynomial time. NP contains P. Most experts believe that the two classes are different, but nobody has found a proof of this.

Rationale

If P=NP then creativity (in almost every conceivable discipline) can be automated. Cryptography becomes impossible. Trying to understand the relationship of P and NP seems fundamental to understanding computation. This question seems to be a problem about the notion of computation itself, not merely about a specific model (such as Turing machine).

Contributors and Credits

Sanjeev Arora

 

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

%d bloggers like this: