Randomized Input Algorithms
Randomized input algorithms fall into four major categories of algorithms using a random selection of inputs:
Interactive proofs are systems in which there is a verifier (or tester) that is trying to establish a proof's soundness and completeness and a prover that answers each challenge. In each round the verifier gives the prover a random problem, and then tests to see whether the answer returned is correct.
Random sampling attempts to discover whether the members of a set S have a certain property by randomly choosing a member from that set and testing it. Repetition of this process can give some confidence to the conclusion that the set does have that property, but without testing every member, there is no certainty.
Abundance of witnesses tests to see whether some input has a certain property (i.e., whether it is a composite) by finding a witness that can attest to that property. Failure to find a witness within a few trials suggests (but does not prove) that the input does not have that property. For example, a witness to some input's compositeness would be a number by which the input is evenly divisible.