United Technologies Engineering Building, Room 150 Storrs, CT Computational complexity was originally defined in terms of the natural entities of time and space, and the term complexity was used to denote the time or space used in the computation. It is startling how closely tied they are when the latter refers to expressing the property in first-order logic. We will explain some of the tight relationships between describing versus computing. Classical Complexity Classes are defined in terms of the complexity of checking whether the input satisfies a certain property. The object is repeatedly modified by users and computations are performed.
Descriptive complexity offers a clean approach to understanding dynamic problems.
An exciting application of Descriptive Complexity is to a part of Computer-Aided Verification called Model Checking. For a long time the area of formal methods had a reputation of claiming more than it could deliver. Now, model checking has come along as an extremely modest approach to formal methods. In fact, it is so modest that it is practical and useful. Many hardware design companies including Intel have adopted model checking as part of their basic design method, and the area is taking off.