Cryptography Reference
In-Depth Information
P
is the class of languages that can be recognized in (deterministic) polynomial
time.
Likewise, the complexity class
is associated with computational problems having
solutions that, once given, can be efficiently tested for validity. It is customary to
define
NP
as the class of languages that can be recognized by a non-deterministic
polynomial-time Turing machine. A more fundamental formulation of
NP
NP
is given by
the following equivalent definition.
Definition 1.3.2 (Complexity Class
NNNP
):
A language L is in
NP
if there exists
}
∗
×{
}
∗
and a polynomial p
(
a Boolean relation R
L
⊆{
)
such that R
L
can
be recognized in (deterministic) polynomial time, and x
∈
L if and only if there
exists a y such that
|
y
|≤
p
(
|
x
|
)
and
(
x
,
y
)
∈
R
L
. Such a y is called a
witness
for membership
of x
∈
L.
0
,
1
0
,
1
·
NP
Thus,
consists of the set of languages for which there exist short proofs of member-
ship that can be efficiently verified. It is widely believed that
P
=
NP
, and resolution
of this issue is certainly the most intriguing open problem in computer science. If indeed
P
=
NP
, then there exists a language
L
∈
NP
such that every algorithm recognizing
L
will have a super-polynomial running time
in the worst case
. Certainly, all
NP
-
complete languages (defined next) will have super-polynomial-time complexity
in the
worst case
.
Definition 1.3.3 (
NNNP
-Completeness):
A language is
NP
-
complete
if it is in
NP
is polynomially reducible to it. A language L
is
polynomially reducible
to a language L
if there exists a polynomial-time-
computable function f such that x
and every language in
NP
∈
L if and only if f
(
x
)
∈
L
.
Among the languages known to be
-complete are
Satisfiability
(of propositional
formulae),
Graph Colorability
, and
Graph Hamiltonicity
.
NP
1.3.2. Probabilistic Polynomial Time
Randomized algorithms play a central role in cryptography. They are needed in or-
der to allow the legitimate parties to generate secrets and are therefore allowed also
to the adversaries. The reader is assumed to be familiar and comfortable with such
algorithms.
1.3.2.1. Randomized Algorithms: An Example
To demonstrate the notion of a randomized algorithm, we present a simple randomized
algorithm for deciding whether or not a given (undirected) graph is connected (i.e., there
is a path between each pair of vertices in the graph). We comment that the following
algorithm is interesting because it uses significantly less space than the standard (BFS
or DFS-based) deterministic algorithms.
