[EM] river, ROACC (terminolgy, again)

[Warren Schudy]

On Sat, 28 Aug 2004, Paul Kislanko wrote:

> James Green-Armytage wrote in response to someone else:
> 
> >Just to repeat myself [another time ;-] : We must consider
> >NON-DETERMINISTIC methods like ROACC (see my post on the
> >"recommendations" thread)
> 
> "Non-Deterministic" is not a synonym for "method with a random component."
> In mathematical logic a "non-deterministic" method is one that solves a
> problem, but for which the complexity of the solution cannot be judged by
> the input to the problem.
> 
> Thus a problem is "NP" if it can be solved in non-deterministic polynomial
> time, meaning in general it can't be known what the degree of the polynomial
> is just from looking at the input.

Your characterization of NP is incorrect. "Non-deterministic" in the
non-deterministic-polynomial (NP) complexity class refers to algorithms
that can be solved in polynomial time on a non-deterministic turing
machine. Please review your complexity theory. As usual, wikipedia has a
good discussion of these matters:

http://en.wikipedia.org/wiki/Non-deterministic_Turing_machine 
http://en.wikipedia.org/wiki/NP_%28complexity%29


I'm not entirely sure what the phrase "non-deterministic" means. I've seen 
it used for two meanings:
-When computing something, avoiding making a decision by making all
possible decisions (back-tracking, non-deterministic turing machines)
-Using chance/randomness

To avoid this ambiguity, I suggest we use a different term for describing 
algorithms that use chance, such as "randomized".

-wjs

/-----------------------------------------\
| Warren Schudy                           |
| WPI Class of 2005                       |
| Physics and computer science major      |
| AIM: WJSchudy  email: wschudy at wpi.edu   |
| http://users.wpi.edu/~wschudy/          |
\-----------------------------------------/