Cryptography Reference
In-Depth Information
Polynomial-time Turing machines work in a deterministic way, meaning that
they repeatedly execute one (or several) deterministic step(s). This need not be the
case, and there are at least two alternative types of Turing machines.
Nondeterministic Turing machine:
This is a polynomial-time Turing machine
that works in a nondeterministic way.
Probabilistic Turing machine:
This is a polynomial-time Turing machine that
works in a probabilistic way.
A nondeterministic Turing machine is arbitrary parallel, works in a nonde-
terministic way, and is able to solve a computational problem if such a solution
exists. The existence of a nondeterministic Turing machine is a purely theoretical
assumption, and it is generally not possible to build such a machine. Contrary to
that, a probabilistic Turing machine can be built. It works in a probabilistic (and
nondeterministic) way. Similar to a deterministic Turing machine, a probabilistic
Turing machine may have a plural of tapes. One of these tapes is called
random tape
and contains uniformly distributed random symbols. During the scanning of an input
instance, the machine interacts with the random tape, picks up a random string, and
then proceeds like a deterministic Turing machine. The random string is called the
random input
to the probabilistic Turing machine (in practice, the random input is
generated by a random or pseudorandom bit generator). With the involvement of
the random input, the recognition of an instance by a probabilistic Turing machine
is no longer a deterministic function of the instance, but is associated with a ran-
dom variable (i.e., a function of the Turing machine's random input). This random
variable typically assigns error probabilities to the event of recognizing the problem
instance (this is explored further later). Remarkably, there are many problems for
which probabilistic Turing machines can be constructed that are more efficient, both
in terms of time and space, than the best known deterministic counterparts. Conse-
quently, probabilistic Turing machines are an important field of study in complexity
theory and have many cryptographic applications.
Last but not least, it is important to note that there are computational models
that are not equivalent to the models itemized at the beginning of this section (in
fact, they are more powerful). Examples include quantum computers and DNA
computers.
•
A
quantum computer
is a computational device that makes use of quantum
mechanical principles to solve computational problems. A “conventional”
computer operates on bits that represent either 0 or 1. In contrast, a quantum
computer operates on
quantum bits
(qubits) that represent vectors in the two-
dimensional Hilbert space. More specifically, a qubit is a linear combination
or
superposition
of
|
0
and
|
1
(with
|
0
and
|
1
representing an orthonormal
