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.

## No comments:

Post a Comment