= One-sided error
A randomized decision algorithm has one-sided error when one answer is always correct and only the other answer can be mistaken.
The guarantee concerns each fixed <input>, with <probability> taken over the choices of the <randomized algorithm>. Always state which answer is protected. In <polynomial identity testing>, call an <input> positive when its <polynomial> is identically zero, and let acceptance mean claiming an identity. Then the possibilities are:
|| Actual <polynomial>
|| Accept: claim identity
|| Reject: claim nonidentity
| Identically zero
| Always correct; every trial accepts.
| Impossible with exact <polynomial evaluation>.
| Nonzero
| Possible mistake if the chosen point is a zero.
| Always correct; the point is a witness.
Thus a zero <polynomial evaluation> can leave uncertainty, but a nonzero <polynomial evaluation> settles the question. An error bound for a fixed nonzero <polynomial> is not the <conditional probability> that a particular accepted <input> is an identity; that latter question would need a distribution on the <inputs> as well.
In <computational complexity theory>, a <polynomial-time algorithm> with this orientation and false acceptance <probability> at most $1/2$ establishes membership in <co-RP>. Reversing the question to ask whether the <polynomial> is nonzero gives the <RP> orientation: negative instances are always rejected. The <random evaluation test for a polynomial identity> explains the required <field>, <total degree>, sampling and evaluation assumptions.
Back to article page
