The complexity of feature-rich systems

Posted by Diego Assencio on 2015.10.05 under Technology (General)

Anyone who works with technology knows intuitively that as more features are added to a system, its complexity increases rather fast and often in unpredictable ways. Given that the more complex a system is, the more susceptible it is to incorrect or suboptimal functioning due to an improper interaction of its features, one is lead to wonder: how fast does the complexity of a system actually grow with the addition of new features?

Even if an exact quantification of the complexity of a given system could be properly defined, its computation would certainly require us to understand the system in its entirety, which is not exactly what we are aiming at here. Consider instead this simple question: for a system having $n$ features, how many pairwise feature interactions are possible?

The question may sound too abstract, so let us motivate it first. For that, consider a car. If one steps on the gas pedal while the parking brake is activated, the car may even move, but slower than if the parking brake would be released. The car may even get physically damaged as a result of operating in this mode for too long. This means two features of the system (the gas pedal and the parking brake) lead to a suboptimal functioning of the car when in the state "gas pedal pressed down" with "parking brake activated".

The example just given illustrates just one of the many possible interactions which can happen between the features of a car. A car is a complex system, and understanding how its features interact is necessary for its proper operation. If a car has $n$ features in total, the number of pairwise feature interactions $N^{(2)}$ is the total number of possible combinations of two from the $n$ features: $$ \displaystyle N^{(2)} = \left(\matrix{n \\ 2}\right) = \frac{n!}{2!(n-2)!} = \frac{n(n-1)}{2} = \frac{1}{2}(n^2 - n) $$ This result is already alarming: the number of pairwise feature interactions grows quadratically with the number of features. The natural question which follows is: what is the number of possible interactions $N^{(3)}$ involving three features? The answer is the total number of possible combinations of three from the $n$ features: $$ \displaystyle N^{(3)} = \left(\matrix{n \\ 3}\right) = \frac{n!}{3!(n-3)!} = \frac{n(n-1)(n-2)}{6} = \frac{1}{6}(n^3 -3n^2 + 2n) $$ Things are now even worse: the complexity of our system grows cubically with the number of features. Let us then go ahead and compute the total number $N$ of possible interactions over any possible subset of features of the system: $$ \begin{eqnarray} N &=& N^{(2)} + N^{(3)} + \ldots + N^{(n)} \nonumber\\[5pt] &=& \displaystyle \left(\matrix{n \\ 2}\right) + \left(\matrix{n \\ 3}\right) + \ldots + \left(\matrix{n \\ n}\right) \nonumber\\[5pt] &=& \sum_{k=0}^n \left(\matrix{n \\ k}\right) - \left(\matrix{n \\ 1}\right) - \left(\matrix{n \\ 0}\right) \label{post_bd2985d293fcd5959b3b4f4f36d3965a_eq_deriv_N} \end{eqnarray} $$ We can now use the binomial theorem to compute the sum on the last line of the equation above: $$ \displaystyle (x + y)^n = \sum_{k=0}^n \left(\matrix{n \\ k}\right)x^{n-k}y^k $$ Taking $x = y = 1$, we have then that: $$ \displaystyle (1 + 1)^n = 2^n = \sum_{k=0}^n \left(\matrix{n \\ k}\right) \label{post_bd2985d293fcd5959b3b4f4f36d3965a_eq_binom_theorem} $$ The right-hand side of equation \eqref{post_bd2985d293fcd5959b3b4f4f36d3965a_eq_binom_theorem} is exactly the sum which appears on the last line of equation \eqref{post_bd2985d293fcd5959b3b4f4f36d3965a_eq_deriv_N}. Therefore: $$ \boxed{N = 2^n - n - 1} $$ As $n$ grows, the value of $N$ quickly becomes dominated by the term $2^n$, i.e., the number of possible feature interactions grows exponentially with the number of features.

Although simplistic, the analysis above has dramatic consequences to the development and testing of new technologies. As more features are added to a system, the number of possible interactions between its features grows so fast that it becomes quickly impossible for the human mind to fully comprehend the system as a whole. Testing its usage under all possible scenarios may become not just difficult, but impractical. As a result, unforeseen problems may end up appearing in the production version of the system — some of which may be really embarrassing for those who designed them.


No comments posted yet.