X-Message-Number: 8574
Date: Wed, 10 Sep 1997 14:30:49 -0400
From: "John P. Pietrzak" <>
Subject: PpP = P (PP = P?)
References: <>

Peter Merel writes:
[on non-determinism]
> 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.

Actually, the non-determinism I'm thinking of is a way of choosing what
to do, not a partitioning over the space of problems.  In other words,
you can use it on trivial problems as well as intractable ones.

For example, in the world of finite state automata, you can only move
from your current state to a particular subsequent state on a given
input (if you are acting in a deterministic way).  Non-determinism
allows you to possibly choose several different states on an input;
you have to choose the "right" one.  However, if there's, say, only
one other state in the entire machine, your choices are going to be
pretty darn trivial whether or not you use non-determinism.

> Hey, while all this computing is vital to us geeks, does anyone
> here know anything about that funky cryonics stuff?

What?  You mean this isn't a 'Theory of Computing' discussion list?
Darn, I hate it when I get these things mixed up.  ;)


John

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