Arguments for or against a trend in the evolution of complexity are weakened by the lack of an unambiguous definition of complexity. Such definitions abound for both dynamical systems and biological organisms, but have drawbacks of either a conceptual or a practical nature. Physical complexity, a measure based on automata theory and information theory, is a simple and intuitive measure of the amount of information that an organism stores, in its genome, about the environment in which it evolves. It is argued that physical complexity must increase in molecular evolution of asexual organisms in a single niche if the environment does not change, due to natural selection. It is possible that complexity decreases in co-evolving systems as well as at high mutation rates, in sexual populations, and in time-dependent landscapes. However, it is reasoned that these factors usually help, rather than hinder, the evolution of complexity, and that a theory of physical complexity for co-evolving species will reveal an overall trend towards higher complexity in biological evolution. Copyright 2002 Wiley-Periodicals, Inc.