Short Answer: Until we have a proof that P≠NP or a proof that P=NP, we cannot rule out the possibility that the P versus NP question is not provable in one of the standard logical theories. However, I firmly believe there exists a proof that P≠NP. To think that the question is not provable just because we are not smart enough to prove it is a cop-out.

You'll have to be patient for the long answer. The October 2003 BEATCS Complexity Column will be devoted to this topic.

## No comments:

## Post a Comment