Logic Seminar
Cameron Hill
University of Notre Dame
Geometric model theory in efficient computability.
Abstract: This talk will consist of a sketch 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 infinite structures. To remove any suspense, the statement of the theorem is as follows:
Theorem.
Let $K = fin[T G]$, where $T$ is a complete $k$-variable theory with infinitely many finite models up to isomorphism.
I. If $T$ is constructible, then $K$ is rosy.
II. $T$ is efficiently constructible if and only if $K$ is super-rosy.
Obviously, a great number of definitions are needed (regardless of the readers background, most likely) to make sense of these assertions. For the time being, it should be understood as a shadow of the "main current of first-order model theory" namely, Shelah's Classification theory. I take "efficiently constructible" meaning that models of $T$ can be efficiently recovered from elementary diagrams of subsets to be a reasonable substitute for "classifable" in the classical theory. We then seek a hierarchy of structural properties culminating in efficient constructibility in analogy with the stability-theoretic hierarchy, Stable $\supset$ Super-stable $\supset$ Classifable = Super-stable + NDOP. In the classical scenario, any non-trivial bound on the number of models of the theory in each cardinality imposes stability, which already supports the rudimentary notion of geometry known as non-forking independence. In the scenario of this study, the hypothesis of constructibility by an algorithm cursorily imitating that of an efficient algorithm in form (meaning, a practically-inationary program which isn't necessarily efficient) is sufficient to impose another rudimentary notion of geometry on the class of models in this case, known as independence in a rosy class; this is the content of I of the theorem. The further requirement of efficiency "polynomially-bounded running times" induces a further guarantee of good behavior in the geometry of independence, and the only if portion of II of the theorem amounts to just this fact. It turns out, then, that this additional tractability in the geometry gives enough purchase to devise an efficient algorithm, initially disguised as a weak model-theoretic coordinatization result, for the class of the theory's finite models.
Tuesday November 23, 2010 at 4:00 PM in SEO 612