On Problem Complexity
Milton Waxman, Ph. D.
8 April, 1996
This paper gives an operational definition for and a measure of problem
complexity together with some discussion of the application. I would
appreciate comments.
Definition of Problem Complexity
Given a problem related to the operation of a given system. The Problem
Complexity or difficulty of the problem is determined by the unknown
elements; i.e., components, relationships, forces, interactions, and
constraints of the system that the problem solver has to determine. The
unknowns are the difference between what the problem solver knows and
what is adequate knowledge about the system in order to solve the
problem. The knowledge of the problem solver is imbedded in the problem
solver's model of the system.
Every problem involves a model, however simple or complicated, correct
or incorrect, of the system to which the problem is related. Once
everything that is needed is known about a system; that is, when one
has an adequate model of it, then problems involving the system are no
longer complex, but solving the problems can still be very complicated
and involve a great amount of work.
The complexity of a problem is a subjective matter. Two people having
different models or views of a system and thus having different sets of
unknowns will have different ideas of the complexity of solving a
problem of the system.
A problem with a car not starting might be very complex for a "Rocket
Scientist" but not for the corner mechanic. On the other hand, I have
known Rocket Scientists who were able to solve car problems that were
too complex for the corner mechanic. In each case, it is the unknowns
in their respective models of the car which determine their ability to
solve the particular car starting problem.
We may never be able to have a true model of a system. However, all one
needs to solve a problem is an adequate model of the system for the
problem complexity to vanish. Thus two people with different models of
a system could each have zero problem complexity, even though neither
one had a true model of the system.
Measure of Problem Complexity
The measure of the complexity of a problem should reflect the
difficulty of determining the unknowns. Therefore, I propose using the
sum of the work needed to determine the unknowns as the "Problem
Complexity" measure. The work could be measured in any convenient way;
e.g., ergs, person-hours, person-weeks, schedule-days, etc.
Then if there are two unknowns, each of which take a person week to
determine, the complexity is two person weeks. If one unknown requires
only one-half person week while the other requires one and one-half
person weeks, the total problem complexity would still be two person
weeks.If there are 'n' unknowns, then one would sum the work for
determining each unknown to get the complexity of the problem.
C = [W(x1) + W(x2) + ... + W(xn)]
This assumes that the unknowns are independent; that is learning about
one of the unknowns does not affect the work of determining the other
unknown.
If the unknowns have a dependency, then for the two unknowns case, one
should look at the work required to determine each of them, given that
the other is known. Then take the minimum of the sum of the costs of
learning both unknowns.
C = Min (x,y) {[W(x) + W(y|x)], [W(y) + W(x|y)]}
As an example, consider a crossword puzzle where one needs to learn a
word down and one that crosses it horizontally. Getting one of the two
words helps in getting the other.
Similarly for the case of more than two unknowns, find the minimum
amount of work for determining all the unknowns given the (various)
amounts of knowledge one has about the other unknowns. This would allow
setting a priority on the way one should work to solve a problem.
If there is a probability associated with the work involved in
determining the unknowns, that should be factored in, also. That is,
weighting the work required to determine each unknown according to the
probabilities involved.
Once the unknowns have been determined, there may still be a lot of
work required to obtain the answer to one's problem. That is the work
in determining the results of the process, a strictly mechanical
operation that has no complexity, albeit a lot of effort may be
involved.
In general, one could only estimate the work involved in determining
the unknowns. In some cases; e. g. running a computer program to
evaluate a function, the amount of work required could be known
precisely.
Notes on the Definition of Problem Complexity:
Consider the problem of the prediction of planetary motion. Astronomers
had a very complex problem in predicting planetary motion until Newton.
When Newton came up with his three laws of motion: those great
complexities of predicting planetary motion disappeared because the
unknowns were found. In this case the forces identified in the three
laws were the unknowns.
The adequacy of the model can also change as more detailed information
is required. An example of this, again from the problem of predicting
planetary motion. Einstein's Theory of Relativity provided the
information on the hitherto unknown forces which gave a basis for
solving the problem of the Precession of the Perihelion of Mercury.
A higher level of problem complexity would be the "Unk-Unks"; the
Unknown Unknowns, those whose very existence is unknown. For example, a
commander might be concerned about the size of an opposing force
directly ahead and not know of another force on the flanks.
The Problem Complexity depends on what the problem solver needs to know
in order to get a solution. If the problem is to get a theoretical
solution, the unknowns may be one thing , while if the problem is to
get a practical solution, they may be another set entirely.
Consider the problem of inverting a large matrix. The theoretical
solution for inverting a matrix is in elementary mathematics text
books. It is useful for small matrices, so here the problem of getting
a theoretical solution and the problem of getting a practical solution
have the same unknowns. But the theoretical solution only works
efficiently enough to be useful for special cases of large matrices;
e.g., Poisson process matrices.
For large general matrices the theoretical solution procedure is not
practical. The unknowns in this case turn out to be that of determining
how to go through a very lengthy process and get the right answer. The
problem of determining a useful procedure is still complex because of
the unknowns related to such things as developing alternative
algorithms for the solution, maintaining the required precision in the
data, achieving the processing speed required for practical use, etc.
For complex distributed systems; e.g., large scale computer models,
where one knows exactly the rules and set up of each individual agent,
there are no unknowns. Thus there is no problem complexity. Determining
the outcome of running the model is strictly a mechanical process that
can be done by an automaton.
The Entscheidlungen Problem or Halting Problem may be an example of
infinite complexity since we know there is no solution. No finite
amount of effort is enough to determine the unknowns.
Acknowledgment
I received extremely valuable criticism which helped me to clarify my
definition of problem complexity through (E-mail) discussions with
Prof. Bruce Edmonds of the Centre for Policy Modelling at Manchester
Metropolitan University, Manchester, UK.
Milton Waxman, Ph. D.
Sierota Systems: Developers of the Genius Handbook (TM)
Creativity In Products and Processes To Increase The Bottom Line
Technique 1.0 Always Consider Local Conditions
Technique 2.0 Always Test The Constraints
Tel: 201-560-9072
114 Parsippany Road
Whippany, NJ 07981
Internet: waxman@ix.netcom.com
(c) 1996, M. J. Waxman, unpublished work, all rights reserved