Finitely unstable theories and computational complexity

Tuomo Kauranne

Published 2014-10-18Version 1

The complexity class $NP$ can be logically characterized both through existential second order logic $SO\exists$, as proven by Fagin, and through simulating a Turing machine via the satisfiability problem of propositional logic SAT, as proven by Cook. Both theorems involve encoding a Turing machine by a formula in the corresponding logic and stating that a model of this formula exists if and only if the Turing machine halts, i.e. the formula is satisfiable iff the Turing machine accepts its input. Trakhtenbrot's theorem does the same in first order logic $FO$. Such different orders of encoding are possible because the set of all possible configurations of any Turing machine up to any given finite time instant can be defined by a finite set of propositional variables, or is locally represented by a model of fixed finite size. In the current paper, we first encode such time-limited computations of a deterministic Turing machine (DTM) in first order logic. We then take a closer look at DTMs that solve SAT. When the length of the input string to such a DTM that contains effectively encoded instances of SAT is parameterized by the natural number $M$, we proceed to show that the corresponding $FO$ theory $SAT_M$ has a lower bound on the size of its models that grows almost exponentially with $M$. This lower bound on model size also translates into a lower bound on the deterministic time complexity of SAT.