UC Berkeley

This dissertation consists of the proof of a single main result linking geometric ideas from the first-order model theory of infinite structures with complexity-theoretic analyses of problems over classes of finite structures. More precisely, we show that for a complete finite-variable theory of finite structures, models are efficiently recoverable from elementary diagrams if and only if the theory is super-rosy. In the course of the argument, we reconstitute the machinery of \th-independence and rosiness for classes of finite-structures, as well as a characterization of rosy classes analogous to the Independence theorem for the simple theories. We show that a super-rosy theory admits a weak form of model-theoretic coordinatization, which can be converted into to an algorithm for the model-building problem mentioned above in a natural and intuitive way. Conversely, we show how to extract a model-theoretic independence relation directly from an efficient algorithm for the model-building problem.