Cryptography Reference
In-Depth Information
hold regardless of the computational model in use (as long as it is “reasonable” in
one way or another). More specifically, the thesis says that any physical computing
device can be simulated by a Turing machine (in a number of steps polynomial in
the resources used by the computing device).
For the rest of this chapter, we associate the Turing machine
M
with the
function
f
M
it computes, and we sometimes write
M
(
x
) instead of
f
M
(
x
) for a
given input
x
. As mentioned earlier, there are several things a Turing machine
M
can do, including, for example, computing a function, solving a search problem, or
making a decision:
}
∗
→{
}
∗
.
•
A Turing machine
M
can
compute a function
f
:
{
0
,
1
0
,
1
}
∗
, and it computes and outputs
In this case,
M
is given input
x
∈{
0
,
1
f
M
(
x
)=
y
∈{
0
,
1
}
∗
.
•
A Turing machine
M
can
solve a search problem
S
⊆{
0
,
1
}
∗
×{
0
,
1
}
∗
.
}
∗
In this case,
M
is given input
x
∈{
0
,
1
that has a solution
y
(i.e.,
S
), and it computes and outputs a solution
f
M
(
x
)=
y
∈{
}
∗
(
x, y
)
∈
0
,
1
with (
x, y
)
∈
S
.
}
∗
. In this case,
•
A Turing machine
M
can
solve a decision problem
D
⊆{
0
,
1
}
∗
, and it determines and outputs a bit saying
M
is given input
x
∈{
0
,
1
whether
x
∈
D
(i.e.,
f
M
(
x
)=1if and only if
x
∈
D
).
In theoretical computer science, a formal language
L
is usually defined as a
subset of Σ
∗
with Σ=
{
0
,
1
}
:
}
∗
L
⊆{
0
,
1
Consequently, a decision problem can also be interpreted as a language mem-
bership problem when the problem instances are encoded as binary strings using
an arbitrary but fixed encoding. For example, all binary encoded prime numbers
represent a formal language, and the decision problem whether a number is prime
or not can also be understood as a membership problem for this particular language.
For the sake of simplicity, complexity theorists usually focus on decision
problems (i.e., problems that have either 1 (yes) or 0 (no) as an answer). This is
not too restrictive, because all computational problems can be phrased as decision
problems in such a way that an efficient algorithm for the decision problem yields
an efficient algorithm for the computational problem, and vice versa.
