#### Milestone Year

### 1990

#### The power of interactive proofs

The traditional view of proofs is that they are texts that one reads
in order to get convinced of the validity of a (formal) assertion.
A more general framework allows arbitrary interaction between the
verifier and the prover, and furthermore allows the verifier to be
convinced of statistical evidence (and in particular toss coins).
Hence, these proofs are randomized and dynamic processes
rather than static objects.

This untraditional notion of proof systems was put forward
by a WIS scientist and her collaborators in 1983 in order to allow for
the introduction of zero-knowledge proofs (see Zero-Knowledge),
but it turns out that it also increases the expressive power of the systems.

First indication to the increased power of interactive proofs
was provided by a WIS scientist and his collaborators in 1986
when showing that such proofs
exist for assertions that are not known to have traditional proofs.
The ultimate demonstration came in 1990, when a WIS scientist showed
that interactive proofs can be provided for any assertion that
can be verified by a computation that consumes a feasible amount
of work-space (but possibly an infeasible amount of time).