[EM] river, ROACC (terminolgy, again)

[Paul Kislanko]

My characterization of NP is exactly the same as what is claimed in the
article. 

In any case, my objection was to the use of "non-deterministic" on this list
as equivalent to "having a random component."


Many systems are "non-deterministic" by the definition given in Wikipedia,
but they do not have a "random" component (especially in the case of the
idealized Turing Machine, which isn't subject to gamma rays switching it's
bits from one state to another).

But a system that involves introducing a random input at any stage cannot be
processed by a Turing Machine, so it is, as I said "Oracular" (and you are
allowed anything for your "Oracle", including picking ballots out of a hat
or consulting a Ouija board, or cutting a deck of cards, or... well, you see
what I mean.)

I was objecting to the term "non-deterministic" being used to apply to an
algorithm that can't be processed by a Turing Machine, which as has been
pointed out is a pre-requisite for the use of the term, which is what is
what I was trying to say in the first place.

I repeat, an EM that has a "randomly select" in its definition is not
"non-deterministic". It is Oracular.

-----Original Message-----
From: election-methods-electorama.com-bounces at electorama.com
[mailto:election-methods-electorama.com-bounces at electorama.com] On Behalf Of
Warren Schudy
Sent: Saturday, August 28, 2004 3:13 PM
To: Paul Kislanko
Cc: election-methods-electorama.com at electorama.com
Subject: RE: [EM] river, ROACC (terminolgy, again)

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/          |
\-----------------------------------------/


----
Election-methods mailing list - see http://electorama.com/em for list info