[EM] river, ROACC (terminolgy, again)
Paul Kislanko
kislanko at airmail.net
Sat Aug 28 13:49:46 PDT 2004
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
More information about the Election-Methods
mailing list