Cryptography Reference
In-Depth Information
6.6
COMPLEXITY CLASSES
In the previous section we introduced deterministic, nondeterministic, and proba-
bilistic polynomial-time Turing machines. These machines can be used to define
complexity classes. In short, deterministic polynomial-time Turing machines can
be used to define the complexity class
, nondeterministic polynomial-time Tur-
ing machines can be used to define the complexity class
P
), and
probabilistic polynomial-time Turing machines can be used to define the complexity
class
NP
(and co
NP
and its subclasses. All of these classes are overviewed, discussed, and put
into perspective next. For the sake of simplicity, we only focus on Turing machines
and decision problems. Note, however, that it is also possible to formally define
the previously mentioned complexity classes on the basis of algorithms (instead of
Turing machines) and for problems other than decision problems.
PP
6.6.1
Complexity Class
P
As suggested in Definition 6.6, the complexity class
(“polynomial-time”) assumes
the existence of deterministic polynomial-time Turing machines.
P
Definition 6.6 (Complexity class
P
)
The complexity class
P
refers to the class
}
∗
that are solvable in polynomial time by a
deterministic Turing machine (i.e., there exists a deterministic polynomial-time
Turing machine
M
with
M
(
x
)=1
if and only if
x
of decision problems
D
⊆{
0
,
1
∈
D
).
comprises all problems that can be
solved deterministically in polynomial time. Similar to Definition 6.6, one can define
the complexity class
Consequently, the complexity class
P
to comprise the class of functions or search problems that are
computable or solvable in polynomial time. This is not done in this topic.
P
6.6.2
Complexity Classes
NP
and co
NP
As suggested in Definition 6.7, the complexity class
(“nondeterministic
polynomial-time”) assumes the existence of nondeterministic Turing machines.
NP
Definition 6.7 (Complexity class
NP
)
The complexity class
NP
refers to the
}
∗
that are solvable in polynomial time by
a nondeterministic Turing machine (i.e., there exists a nondeterministic polynomial-
time Turing machine
M
with
M
(
x
)=1
if and only if
x
class of decision problems
D
⊆{
0
,
1
∈
D
).
As mentioned earlier, nondeterministic Turing machines are purely theoretical
constructs, and it is currently not known how to build such a machine. Consequently,
