COMPLEXITY MADE SIMPLE*
*AT A SMALL PRICE
There are some fundamental complexity limits that provide a starting point for any effort to solve design, control, and optimization problems that involve complex dynamic systems. The goal of this lecture is to show that there are ways to solve many hard problems by exploiting their specific structure, by asking the “right” questions, and by challenging some conventional approaches.
First, trial-and-error techniques are often used to systematically learn and predict the behavior of a complex system. These are invariably slow, inefficient, and intrusive. However, this learning can sometimes be accomplished at a fraction of the usual brute-force trial-and-error process through simple “thought experiments” constructed at a “small price.” This is particularly true for Discrete Event Systems, regardless of the modeling framework (automata, Petri Nets, or other) one chooses to employ.
Second, it is known that decomposition and abstraction methods can sometimes provide accurate solutions or significantly simplify a hard problem at the “small price” of some loss of accuracy. Such methods can be used in large distributed systems and, in some cases, this “small price” can be quantified.
Finally, when it comes to today’s wireless, networked world, conventional time-driven methods for sampling, control, and communication should be challenged. For example, communication actions dictated solely by a “clock” drain precious battery power, exacerbate security risks, and are often unnecessary; they may be instead event-driven at the “small price” of identifying the proper events triggering these actions. In this vein, an interesting question is “what is the least amount of information exchange required within a team of cooperating agents to achieve a given goal?” This question will be addressed for a class of problems where the goal is provably met while saving energy and enhancing security.