[EM] river, ROACC (terminolgy, again)

[Paul Kislanko]

This has bugged me for awhile, but it was only some other work that I was
doing that gave expression to what has bugged me about it.

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)

	Okay, I will consider them! : )
---------------------------------------

"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.

The problems classified that way DO have solutions, and they do NOT depend
upon introduction of any random-ness into the algorithms that apply to them.
Those are referred to by other names. 

In particular, at any stage in an algorithm, it is allowed to refer to an
"Oracle." That is an external input not related to the original that allows
the algorithm to find a solution faster.

IRV would be classified as "non-deterministic" since it can't be told in
advance how many rounds would be required to select a winner; any method
that requires a random input would be classified as "oracular."


Thank you for listening. I feel better now.