Cryptography Reference
In-Depth Information
It is obvious to see that an
NP
-complete problem must always be
NP
-hard,
whereas the converse may not be true (i.e., an
NP
-hard problem may not be
NP
-
complete). In fact, there are (decision) problems that are
-
complete. For example, the
halting problem
(i.e., the problem to decide whether a
given program with a given input will halt or run forever) is
NP
-hard but not
NP
NP
-hard but not
NP
-
complete. On one hand, one can show that there exists an
-complete problem
(e.g., the satisfiability problem) that polytime reduces to the halting problem. On
the other hand, one can show that the halting problem is not in
NP
NP
(because all
problems in
NP
must be decidable but the halting problem is not).
6.6.3
Complexity Class
PP
and Its Subclasses
As suggested in Definition 6.12, the complexity class
(“probabilistic polynomial-
time”) comprises all decision problems that can be solved by probabilistic polynomial-
time Turing machines.
PP
Definition 6.12 (Complexity class
PP
)
The complexity class
PP
refers to the
}
∗
that are solvable in polynomial time by
class of decision problems
D
⊆{
0
,
1
a probabilistic Turing machine.
Probabilistic Turing machines implement probabilistic algorithms, and there
are basically three classes of such algorithms:
•
A
Las Vegas algorithm
runs in expected polynomial time (related to the size
of its input) and outputs a result that is always correct. The fact that it runs in
expected polynomial time means that it may not provide a result at all.
•
A
Monte Carlo algorithm
always runs in polynomial time but has only some
probability of providing a correct result. In the case of a decision problem,
a Monte Carlo algorithm is
yes-biased
if a yes answer is only correct with
some probability, whereas a no answer is always correct. Contrary to that, a
Monte Carlo algorithm is
no-biased
if a no answer is only correct with some
probability, whereas a yes answer is always correct.
•
Similar to a Monte Carlo algorithm, an
Atlantic City algorithm
always runs in
polynomial time and has only some probability of providing correct results.
Contrary to a Monte Carlo algorithm, however, an Atlantic City algorithm
may err on either side, meaning that both possible answers (i.e., yes and no)
are only correct with some probability.
In Section 6.5, we argued that the recognition of a problem instance by a
probabilistic Turing machine is not a deterministic function of the problem instance
