Newsgroups: sci.math
From: hoey@pooh.tec.army.mil (Dan Hoey)
Date: 1996/05/21
Subject: Re: [Q:] P, NP, NP-complete, NP-hard; free licks

Rogerio Brito (rbr...@ime.usp.br) wrote:

: jmcca...@sun1307.spd.dsccc.com (Mike McCarty) wrote:

: >  NP can be solved in Polynomial time
: >     with a Nondeterministic Algorithm

: It's good that someone has posted these definitions.  But
: in order to understand them, one needs to  know  what  is
: meant  by  saying that an algorithm is "Deterministic" or
: "Nondeterministic".  As I recall  reading Knuth, vol.  1,
: he says that every algorithm has  to  be  "deterministic"
: (that  is  he says that every algorithm has to present an
: output based on some input).

While Knuth's definition of a (deterministic, nonrandomized) algorithm
has been extended and generalized by many researchers, that is
not particularly relevant to the definition of NP.  The kind of
nondeterministic algorithm that defines NP is a theoretical construct
that bears little or no relation to algorithms for real computers.
Mike McCarty's definition is so vague on this topic as to be
meaningless.  In particular, there is a very similar kind of
theoretical nondeterministic algorithm that gives you a possibly
different class called co-NP, and there is no way to tell from the
above which is meant.

The particulars of this form of nondeterminism are sufficiently subtle
that I do not think it useful to try to explain them here; see Garey
and Johnson or some other theoretical text.  But please don't pretend
to explain what NP is if your explanation does not distinguish it from
co-NP.

Dan Hoey
Hoey@AIC.NRL.Navy.Mil