Appendix A: Mathematical Facts - Codes: The Guide to Secrecy from Ancient to Modern Times - page 503

polynomial time or probabilistic polynomial time . Here,

P ⊆ RP ⊆ NP .

A practical (but mathematically less satisfying) way to define “hard” problems is
to view them as those which have continued to resist solutions after a concerted
attack by competent investigators for a long time up to the present.
Another classification in complexity theory is the NP -complete problem,
which is a problem in the class NP that can be proved to be as diGcult as any
problem in the class. Should an NP -complete problem be discovered to have a
deterministic polynomial-time algorithm for its solution, this would prove that
NP

P ,so P = NP . Hence, we are in the position that there is no proof that
there are any hard problems in this sense, namely, those in NP but not in P .
Nevertheless, this has not prevented the flourishing of research in complexity
theory. The classical NP -complete problem is the travelling salesman problem :
A travelling salesman wants to visit n

⊆

cities. Given the distances between
them, and a bound B , does there exist a tour of all the cities having total length
B or less? The next in the hierarchy of complexity classification is EXPTIME ,
problems that can be solved in exponential time.
Thus far, we have been concerned with the time it takes for an algorithm
to execute, measured (asymptotically, the worst-case scenario) in terms of the
number of bit operations required. Another component of complexity is the
amount of computer memory (storage required) for the computation of a given
algorithm, called the space requirement . Time calculation on a Turing machine
is measured in terms of the number of steps taken before it enters a halt state,
as we have discussed above. The space used is defined as the number of tape
squares visited by the read-write head (where we think of the tape as having
infinitely many squares read, written, or erased by a “read-write head”). Thus,
the notion of polynomial space takes on meaning, and since the number of steps
in a computation is at least as large as the number of tape squares visited, then
any problem solvable in polynomial time is solvable in polynomial space. Thus,
we define PSPACE as those problems that can be solved in polynomial space,
but not necessarily in polynomial time. Hence, PSPACE -complete problems
are those such that if any one of them is in NP , then PSPACE=NP , and
if any one of them is in P , then PSPACE=P . At the top of the hierarchy
of the classification of problems in terms of complexity is EXPSPACE , those
problems solvable in exponential space, but not necessarily in exponential time.
It is known that P

∈ N

= EXPTIME and

NP ⊆ PSPACE = EXPSPACE .

(There are also the nondeterministic versions, NPSPACE and NEX-
PSPACE , which we will not discuss here.) Figure A.1 provides an illustration
of the above discussion on the hierarchy of problems in complexity theory.