Cryptography Reference
In-Depth Information
However, by having instant access to the memory, we “only” gain a factor limited to
the size of the used memory, which is limited to the size of the input and the size
of the intermediate results, which is itself less than the time complexity. This would
have defined the same notion of computable languages, but one language which is
quadratically computable with a single tape could have become linearly computable
with the other. Therefore we only try to distinguish languages which can be accepted
within a complexity which grows “smoothly” from others, with a notion of smooth
growth which is robust with our notion of Turing machine. As Section 8.3.2 shows,
“smooth” means “polynomial” here.
8.3.2
Complexity Classes P, NP, co-NP
Polynomial growth is quite robust. Actually, if we can make a polynomial-time al-
gorithm (in an intuitive sense) which computes the language, then it can also be
implemented on a Turing machine in polynomial time. Therefore the simple Turing
machine model is enough in order to distinguish polynomial time algorithms from
others. We say that a problem defined by
L
is
polynomial
if there exists a polyno-
mial Turing machine which accepts
L
. We let P denote the set of all polynomial lan-
guages.
Interestingly, once we know an upper bound on the complexity of a Turing machine,
we can transform it into a Turing machine which always halts within this complexity
on an acceptance or rejection state. Hence, decision problems become symmetric in
deterministic time.
As already seen, nondeterministic Turing machines define the same notion of
computability. However, the notion of polynomial languages is very different. We let
NP denote the set of all languages which are accepted by a nondeterministic Turing
machine in polynomial time. Saying that a language
L
is accepted by a nondeterministic
Turing machine
M
in polynomial time means that
1. for any word
x
,wehave
x
∈
L
if and only if there exists a running of
M
on
x
which halts
2. there exists an integer
d
such that for any word
x
L
of length
n
there exists a
running of
M
on
x
which halts within a time at most
n
d
∈
Obviously, the class P is included in the NP class since deterministic Turing machines
are special nondeterministic Turing machines. The question whether P is equal to NP or
not is still open. It is considered as one of the most fundamental problems in theoretical
computer science.
It should be emphasized that decision problems are no longer known to be symmet-
ric. (Of course, if P
NP, it is symmetric.) We let co-NP denote the set of all languages
L
such that the complement of
L
is in NP. The decision problem is obviously symmetric
in NP
=
∩
co-NP: for any language
L
in this class, there exists a nondeterministic Turing
Search WWH ::
Custom Search