  A set of stochastic matrices ${\cal P}$ is a consensus set if for every
sequence of matrices $P(1), P(2), \ldots$ whose elements belong to ${\cal P}$
and every initial state $x(0)$, the sequence of states defined by $x(t) = P(t)
P(t-1) \cdots P(1) x(0)$ converges to a vector whose entries are all identical.
In this paper, we introduce an "avoiding set condition" for compact sets of
matrices and prove in our main theorem that this explicit combinatorial
condition is both necessary and sufficient for consensus. We show that several
of the conditions for consensus proposed in the literature can be directly
derived from the avoiding set condition. The avoiding set condition is easy to
check with an elementary algorithm, and so our result also establishes that
consensus is algorithmically decidable. Direct verification of the avoiding set
condition may require more than a polynomial time number of operations. This is
however likely to be the case for any consensus checking algorithm since we
also prove in this paper that unless $P=NP$, consensus cannot be decided in
polynomial time.
