Information Technology Reference
In-Depth Information
attacks, we wish to recognize the presence of malicious code and so on. And
we wish to do it automatically, using algorithms, and these algorithms must be
ecient, and here the complexity arrives. Historically the complexity played an
outstanding role in elaborating many quite pragmatical theories in computer
science.
One can easily remark that in the context of the state-of-the-art of the theory
related to the security itself, as mentioned just above, this enterprise cannot give
genuine insights, to put it mildly. The diculty is also aggravated by the state of
the theory of computational complexity, that, to my mind, is in a relative crisis,
historically quite natural.
What do we really know about the complexity of practical or, at least, con-
crete problems? There is a great intellectual achievement in devising algorithms
that ensure this or that eciency, formulated as upper bounds of the compu-
tational complexity, sometimes in a very detailed manner that facilitates their
estimation from practical viewpoint. As for the lower bounds, the results not
leaning upon intractability conjectures (many of the latter seem to me rather
dubious) are those that state undecidability, high (exponential and above) lower
bounds or hardness with respect to some classes of problems that the majority
of the community is inclined to believe to be worst-case or otherwise dicult.
(Notice that the majority is not always right concerning scientific matters.)
One can easily see that these results are not relevant to practical problems
1
.
Indeed, a typical proof of such a result constructs a subset of problem instances
that model execution of some class of algorithms, usually Turing machines. But
only some diagonal algorithms give the high complexity. So the dicult instances
are based on diagonal algorithmic constructions. No
practical
algorithm, as far
as I am aware, uses diagonal constructions
2
.
The consequence of this irrelevancy remark is that negative results, whatever
be their theoretical importance for crafting a theory, and this role is often undeni-
ably outstanding, should be adequately interpreted vis-a-vis practical problems.
To say it in other words, we are to understand better what is
practical problem
from theoretical viewpoint.
As an example consider how one typically proves that it is undecidable
whether a given program contains a malicious code. Take any program that
do some prescribed work. Append into it a piece of code that is executed 'in
parallel' with the main activity and that checks self-applicability of some other
code
X
, i. e. this parallel activity applies a universal machine that takes
X
as
program and applies it to
. If this process halts then our appended program
behaves as a virus, otherwise it does nothing. As a mass problem over
X
X
,itis
1
A. Pnueli remarked at the workshop on verification in May 2003 in Tel-Aviv that it
would more precise to say that the existing
proofs
of these results are not relevant
to practical problems.
2
One can imagine some algorithms based on diagonal constructions. The most inter-
esting example that I know, is L. levin's 'optimal algorithm' for the SAT (proposi-
tional logic satisfiability) problem — one of the basic NP-complete problems. The
algorithm is optimal modulo a multiplicative constant; a brilliant 'cheating' is in the
size of this constant.
