X-Message-Number: 8572
Date: Wed, 10 Sep 1997 00:01:55 -0700
From: Peter Merel <>
Subject: PP!=NP

John Pietrzak writes,

>Actually, that's not quite true.  One can prove that there is an
>equivalent deterministic finite state automata for each
>non-deterministic finite state automata.  And, in fact, there is also
>a proof that for each non-deterministic Turing Machine, there is an
>equivalent deterministic Turing Machine.  (I guess it depends on what
>sort of non-determinism you are thinking about.)

I think the same sort you're talking about. I said "trivially",
not "feasibly". Without recapitulating the P=NP? question, or as
much of it as I recall from computability 101, I only meant that
emulating non-determinism on a serial computer is not something you
can do in polynomial time. Or at least it wasn't last I heard. But if 
someone's recently resolved P=NP? in the negative I'll happily eat crow.

Hey, while all this computing is vital to us geeks, does anyone
here know anything about that funky cryonics stuff? Might be kinda relevant?
Prometheus update? The cryocare contracts question? Oregonian or South
Australian right to die? Fly lifespans? African or European dewar?

Peter Merel.

Rate This Message: http://www.cryonet.org/cgi-bin/rate.cgi?msg=8572