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