X-Message-Number: 4263
Date: Thu, 20 Apr 1995 21:31:53 -0400
From: "Keith F. Lynch" <>
Subject: Re: Computability and Complexity

Peter Merel <>
> ... but which can be solved in polynomial time on a non-deterministic
> (read "parallel") machine.

Non-deterministic is not the same as parallel.

Parallel computers (including neural nets) are parallel and
deterministic.  If a problem can't be solved in polynomial time on a
serial machine, then it can't be solved in polynomial time on a parallel
machine either.


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