The ``chip problem'' is a fault diagnosis problem in which
we must determine which components (chips) in a system are
defective, assuming the majority of them are good.
Chips are tested as follows: take two chips, say x and
y, and have x report whether y is good or
bad. If x is good, the answer is correct, but if x
is bad, the answer is unreliable and can be either wrong
with probability
or right with probability
1 -
. We show that the chip problem is
closely related to a modified majority problem in the worst
case and use this fact to obtain upper and lower bounds on
algorithms for the chip problem. We show the limits of this
relationship by showing that algorithms for the chip problem
can violate lower bounds on average performance for the
modified majority problem and we give an algorithm for the
``biased chip'' problem (in which p is the probability
that a chip is bad) whose average performance is better than
the average cost of the best algorithm for the biased majority problem.