Cryptography Reference
In-Depth Information
}
∗
=
n∈
N
n
{
0
,
1
{
0
,
1
}
Using the binary alphabet, a positive integer
n
∈
N
can always be encoded as
l
of length
l
:
abinaryword
b
l−
1
...b
1
b
0
∈{
0
,
1
}
l
−
1
b
i
2
i
n
=
i
=0
In complexity theory, a positive integer
n
∈
N
is frequently encoded using the
unary representation
:
n
=1
n
=11
···
1
n
times
The relevant operation for words is the (string) concatenation, denoted as
or
Σ
∗
,then
v
◦
w
results from
concatenating
v
and
w
. The empty word
ε
is the neutral element of the concatenation
operation, hence
v
(in this topic, we use
most of the time). If
v, w
∈
Σ
∗
. It can be shown that
Σ
∗
,
ε
=
ε
v
=
v
for every
v
∈
represents a monoid, as formally introduced in Section 3.1.2.2.
6.2
INTRODUCTION
Complexity theory
is a central field of study in theoretical computer science. Ac-
cording to [4], the
main goal of complexity theory is to provide mechanisms for classify-
ing computational problems according to the resources needed to solve
them. The classification should not depend on a particular computa-
tional model, but rather should measure the intrinsic difficulty of the
problem. The computational may include time, storage space, random
bits, number of processors, etc., but typically the main focus is time,
and sometimes space.
The important points are (
a
) that the computational problems should be clas-
sified according to the resources needed to solve them, and (
b
) that this classification
