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.

Artificial intelligence

On May 7, 1941, the Royal Navy (UK) captured a top-secret German "Enigma" code machine.

They did a lot of work with that in the years to come, calling the project "Ultra."

Alan Turing, a mathematician and logician, was involved in that work, and Turing in time came to generalize this experience in some writings that have had great importance in the subsequent development of computer science.

Thus, one encounters talk of a "turing machine" and of the "Turing test" as a standard for whether artificial intelligence has been achieved.

I don't know what will happen in the politics of the UK as a consequence of the votes cast yesterday. But I do think that (outgoing?) prime minister Gordon Brown deserves some credit for apologizing for the "appalling" way in which Alan Turing was treating as a consequence if Turing's homosexuality.