Information Technology Reference
In-Depth Information
min
lp
ðÞ
:
φ
ð
p
=
x
0
Þ
¼
y
0
,
K
φ
ð
y
0
=
x
0
Þ
¼
1
:
8
p
S
φ
ð
p
=
x
0
Þ 6
¼
y
0
:
∈
Computational complexity of the algorithm describing the behavior of the
system (the complexity of the problem) characterizes the practical feasibility of
understanding the behavior of the system in detail. It can be reduced to the
dependence of computational capacity (resources of the computer system) required
to model the behavior of the system, from the specific characteristics of the
problem—the size of the problem.
Different versions of the functions that characterize the computational complex-
ity (so-called signaling functions) are used for its quantitative assessment. The most
common among them are:
Time function:
t
A
n
ðÞ
¼
max
t
A
x
ðÞ:
x
¼
n
Here
t
A
(
x
) is the number of steps of the program that implements the algorithm
A
to solve the individual problem
x
, whose size is determined by word length |
x
|
equal to
n
.
Spatial function:
S
A
n
ðÞ
¼
max
S
A
x
ðÞ
,
x
¼
n
where
S
A
(
x
) is the number of memory cells required to solve the problem
A
.
The algorithm for solving the mass problem is called polynomial algorithm if the
signaling function depends polynomially on the size of the problem. If, however,
the signaling function depends on the size of the problem exponentially, it is defined
as intractable. At present time a detailed classification of hard problems is utilized
(NP, NP-complete, etc.).
Speaking about the structural and behavioral complexity of an information
processing system and about computational complexity of the tasks being solved
by the system, particular properties of the concept being used should be empha-
sized. Unfortunately, so far no sufficiently strong correlation between these char-
acteristics has been established.
It is popularly believed (mainly in connection with the practice of creating
wireless devices) that increasing complexity of the device leads to more complex
behavior. Nevertheless, today we know a large number of objects in which simple
structure coexists with very complex behavior. The most well-known example is
the H
´
non problem describing the dynamics of two harmonic oscillators with
nonlinear coupling. This seemingly simple system demonstrates a great variety of
different modes, ranging from trivial harmonic vibrations to the state of chaos.
Even more uncertain is the relationship between computational complexity of
problems and the structure of the devices used to solve them, which is particularly
