Cryptography Reference
In-Depth Information
8.3
Complexity Reduction
The most important idea of complexity theory for cryptography is the notion of
prob-
lem reduction
with
oracles
. The question of problem reduction aims at proving that a
problem A is at most as hard as a problem B by showing that an “efficient” algorithm
can solve B when using an imaginary machine (an “oracle”) which can solve A. For
this we must properly define the notion of efficiency and oracle.
4
8.3.1
Asymptotic Time Complexity
Whenever a decision problem is decidable, we can still wonder about the cost of the deci-
sion (or how efficiently we can solve it). A decision problem is defined by a language
L
.
An
instance
of the problem is a word
x
. The problem is to decide whether
x
∈
L
or not.
For a Turing machine
M
which accepts
L
, and for a word
x
in
L
, we consider the
number
T
M
,
x
of steps of
M
with input
x
before halting. For all integers
n
we consider
the maximum
T
(
n
)of
T
M
,
x
over all words
x
∈
L
with length at most
n
. We say that
M
has a
time complexity
of
T
.
We are usually interested in
asymptotic
complexities, which means about the order
of magnitude of the growth of
T
(
n
) when
n
grows. For this we must introduce some
standard notations. Given two functions
f
(
x
) and
g
(
x
) defined over a set of values
x
which is not upper bounded (i.e. in which
x
can grow up to infinity), we let
f
(
x
)
=
O
(
g
(
x
)) if there exist two constants
c
>
0 and
x
0
such that for any
x
≥
x
0
,wehave
|
f
(
x
)
|≤
c
|
g
(
x
)
|
f
(
x
)
=
(
g
(
x
)) if there exist two constants
c
>
0 and
x
0
such that for any
x
≥
x
0
,wehave
|
f
(
x
)
|≥
c
|
g
(
x
)
|
, i.e. if
g
(
x
)
=
O
(
f
(
x
))
f
(
x
)
=
(
g
(
x
)) if we have both
f
(
x
)
=
O
(
g
(
x
)) and
f
(
x
)
=
(
g
(
x
)), i.e. if
there exist three constants
c
1
>
0,
c
2
>
0, and
x
0
such that for any
x
≥
x
0
,we
have
c
1
|
g
(
x
)
|≤|
f
(
x
)
|≤
c
2
|
g
(
x
)
|
f
(
x
)
=
o
(
g
(
x
)) if for any
ε>
0 there exists a constant
x
0
such that for any
x
≥
x
0
,wehave
|
f
(
x
)
|≤
ε
|
g
(
x
)
|
.
=
O
We say that
M
is
linear
if
T
(
n
)
(
n
). Similarly, we say that
M
is
quadratic
(resp.
=
O
(
n
2
) (resp.
T
(
n
)
=
O
(
n
3
)). We say that
M
is
polynomial
if there
cubic
)if
T
(
n
)
exists an integer
d
such that
T
(
n
)
=
O
(
n
d
).
Making a difference between a language which can be accepted in linear time
or in quadratic time is somehow arbitrary because it depends on the intrinsic power
of the Turing machine: we could have defined another computational model with—
say—Turing machines with two tapes instead of one. As we already said, our Turing
machine model wastes time in order to move the head from both ends of the tape.
4
For further reading about this section we recommend Ref. [20].
Search WWH ::
Custom Search