[EM] river, ROACC (terminolgy, again)
Warren Schudy
wschudy at WPI.EDU
Sat Aug 28 13:13:19 PDT 2004
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/ |
\-----------------------------------------/
More information about the Election-Methods
mailing list