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