Time, Hardware, and Uniformity

We describe three orthogonal complexity measures: parallel time, amount of hardware, and degree of non-uniformity, which together parametrize most complexity classes. We show that the descriptive complexity framework neatly captures these measures using three parameters: quantifier depth, number of variables, and type of numeric predicates, respectively. A fairly simple picture arises in which the basic questions in complexity theory --- solved and unsolved --- can be understood as questions about tradeoffs among these three dimensions. 1 Introduction An initial presentation of complexity theory usually makes the implicit assumption that problems, and hence complexity classes, are linearly ordered by "difficulty". In the Chomsky Hierarchy each new type of automaton can decide more languages, and the Time Hierarchy Theorem tells us that adding more time allows a Turing machine to decide more languages. Indeed the word "complexity" is often used (e.g., in the study of algorithms) to mea..