Re: NP-complete and NP-Hard?
Torben Ægidius Mogensen wrote:
> In simple terms, a nondeterministic machine can spawn a new machine
> every time it needs to make a choice, so after n choices, there can be
> 2^n machines. These machines can not communicate, but if any one
> stops with an answer to the problem they are given, we say the problem
> is solved.
>
> NP is the class of problems that can be solved in polynomial time (in
> terms of input size) on such a nondeterministic machine.
Unfortunately, that description loses the distinction between NP
and Co-NP. NP is the set of languages that nondeterministic
machines accept in polynomial time.
--
--Bryan
.
