1. A yes-or-no problem is in P (Poynomial time) if the answer can be computed in polynomial time.
2. A yes-or-no problem is in NP (Non-deterministic Poynomial time) if a yes answer can be verified in polynomial time.

Intuitively, we can see that if a problem is in P, then it is in NP. Given a potential answer for a problem in P, we can verify the answer by simply recalculating the answer.

Less obvious, and much more difficult to answer, is whether all problems in NP are in P. Does the fact that we can verify an answer in polynomial time mean that we can compute that answer in polynomial time?

There are a large number of important problems that are known to be NP-complete (basically, if any these problems are proven to be in P, then all NP problems are proven to be in P). If P = NP, then all of these problems will be proven to have an efficient (polynomial time) solution.

Most scientists believe that P!=NP. However, no proof has yet been established for either P = NP or P!=NP. If anyone provides a proof for either conjecture, they will win $1MM.

1. A yes-or-no problem is in P (Polynomial time) if the answer can be computed in polynomial time.
2. A yes-or-no problem is in NP (Non-deterministic Polynomial time) if a yes answer can be verified in polynomial time.

Intuitively, we can see that if a problem is in P, then it is in NP. Given a potential answer for a problem in P, we can verify the answer by simply recalculating the answer.

Less obvious, and much more difficult to answer, is whether all problems in NP are in P. Does the fact that we can verify an answer in polynomial time mean that we can compute that answer in polynomial time?

There are a large number of important problems that are known to be NP-complete (basically, if any these problems are proven to be in P, then all NP problems are proven to be in P). If P = NP, then all of these problems will be proven to have an efficient (polynomial time) solution.

Most scientists believe that P!=NP. However, no proof has yet been established for either P = NP or P!=NP. If anyone provides a proof for either conjecture, they will win US $1 million.

1. A yes-or-no problem is in P (Poynomial time) if it the answer can be computed in polynomial time.
2. A yes-or-no problem is in NP (Non-deterministic Poynomial time) if a yes answer can be verified in polynomial time.

Intuitively, we can see that if a problem is in P, then it is in NP. Given a potential answer for a problem in P, we can verify the answer by simply recalculating the answer.

Less obvious, and much more difficult to answer, is whether all problems in NP are in P. Does the fact that we can verify an answer in polynomial time mean that we can compute that answer in polynomial time?

There are a large number of important problems that are known to be NP-complete (basically, if any these problems are proven to be in P, then all NP problems are proven to be in P). If P=NP, then all of these problems will be proven to have an efficient (polynomial time) solution.

Most scientists believe that P/=NP. However, no proof has yet been established for either P=NP or P/=NP. If anyone provides a proof for either conjecture, they will win $1MM.

1. A yes-or-no problem is in P (Poynomial time) if the answer can be computed in polynomial time.
2. A yes-or-no problem is in NP (Non-deterministic Poynomial time) if a yes answer can be verified in polynomial time.

Intuitively, we can see that if a problem is in P, then it is in NP. Given a potential answer for a problem in P, we can verify the answer by simply recalculating the answer.

Less obvious, and much more difficult to answer, is whether all problems in NP are in P. Does the fact that we can verify an answer in polynomial time mean that we can compute that answer in polynomial time?

There are a large number of important problems that are known to be NP-complete (basically, if any these problems are proven to be in P, then all NP problems are proven to be in P). If P = NP, then all of these problems will be proven to have an efficient (polynomial time) solution.

Most scientists believe that P!=NP. However, no proof has yet been established for either P = NP or P!=NP. If anyone provides a proof for either conjecture, they will win $1MM.