P/ NP Issue

I wrote about the mathematics of cryptography here in August 2010.

There's a critical and apparently still open issue called the P/NP problem.

I've since learned something else intriguing. This problem may involve the question of whether there is a mathematically provable distinction between time and space.

Walter Savitch, a long-time professor at the University of California, San Diego. Savitch's theorem demonstrates that there is an algorithm for determining whether there is a path between two vertices in a directed graph.

Dexter Kozen, in a book called The Theory of Computation, notes that this has a bearing upon, although it is not identical to, "the most important open question
in theoretical computer science," the question of whether P = NP.

For example, if you define "P" as a set including all easily-solved problems, and "NP" as the set of all problems that can be easily recognized as accurately solved once somebody else has done so, then it seems intuitively obvious that "P" and "NP" are not the same set. If they were the same set, it would be a troubling fact for computer scientists, because it would mean that everything is (in principle) hackable.

Savitch's theorem says that the spatial equivalents of P and NP are equal. The distinction, if any, involves the passage of time.