Cryptography Reference
In-Depth Information
The
joint computation
of a linked pair of ITMs, on a common input x , is a
sequence of pairs representing the local configurations of both machines. That
is, each pair consists of two strings, each representing the local configuration of
one of the machines. In each such pair of local configurations, one machine (not
necessarily the same one) is active, while the other machine is idle. The first pair
in the sequence consists of initial configurations corresponding to the common
input x , with the content of the switch tape set to zero.
If one machine halts while the switch tape still holds its identity, then we say that
both machines have halted. The
outputs
of both machines are determined at that
time.
At this point, the reader may object to this definition, saying that the individual
machines are deprived of individual local inputs (whereas they are given individual
and unshared random tapes). This restriction is removed in Section 4.2.4, and in fact
allowing individual local inputs (in addition to the common shared input) is quite
important (at least as far as practical purposes are concerned). Yet, for a first presentation
of interactive proofs, as well as for demonstrating the power of this concept, we prefer
the foregoing simpler definition. On the other hand, the convention of individual random
tapes is essential to the power of interactive proofs (see Exercise 4).
4.2.1.2. Conventions Regarding Interactive Machines
Typically, we consider executions in which the content of the random tape of each
machine is uniformly and independently chosen (among all infinite bit sequences). The
convention of having an infinite sequence of internal coin tosses should not bother the
reader, because during a finite computation only a finite prefix is read (and matters).
The content of each of these random tapes can be viewed as internal coin tosses of
the corresponding machine (as in the definition of ordinary probabilistic machines
presented in Chapter 1). Hence, interactive machines are in fact probabilistic.
Notation.
Let
A
and
B
be a linked pair of ITMs, and suppose that all possible inter-
actions of
A
and
B
on each common input terminate in a finite number of steps. We
denote by
(
x
) the random variable representing the (local) output of
B
when in-
teracting with machine
A
on common input
x
, when the random input to each machine
is uniformly and independently chosen. (Indeed, this definition is asymmetric, since it
considers only
B
's output.)
Another important convention is to consider the time-complexity of an interactive
machine as a function of only its input's length.
A
,
B
Definition 4.2.3 (The Complexity of an Interactive Machine):
We say that an
interactive machine A has
time-complexity
t
:
N → N
if for every interactive
machine B and every string x , it holds that when interacting with machine B, on
common input x , machine A always (i.e., regardless of the content of its random
tape and B's random tape) halts within t
(
)
steps. In particular, we say that A is
polynomial-time
if there exists a polynomial p such that A has time-complexity p.
|
x
|
