Cryptography Reference
In-Depth Information
Figure A.1: Hierarchy of Problems in Complexity Theory.
✤
✜
✛
✘
✗
✔
✏
EXPSPACE
EXPTIME
PSPACE-complete
PSPACE NP-complete NP
P
✒
✑
✖
✕
✚
✙
✣
✢
There are other types of complexity such as
circuit complexity
, which looks at
the connection between Boolean circuits and Turing machines as a computa-
tional model for studying
P
vis-a-vis
NP
and aGliated problems. We will not
discuss these more advanced themes here.
Roughly speaking, complexity theory can be subdivided into two categories:
(a) structural complexity theory, and (b) the design and analysis of algorithms.
Essentially, category (a) is concerned with lower bounds, and category (b) deals
with upper bounds. Basically, the primary goal of structural complexity theory
is to classify problems into classes determined by their intrinsic computational
diGculty. In other words, how much computing time (and resources) does it
take to solve a given problem? As we have seen, the fundamental question in
structural complexity theory remains unanswered, namely, does
P
=
NP
?We
have been primarily concerned with the analysis of algorithms, which is of the
most practical importance to cryptography.
Search WWH ::
Custom Search