Model theory and complexity theory
by Gomaa, Walid, Ph.D., UNIVERSITY OF MARYLAND, COLLEGE PARK, 2007, 124 pages; 3277368
 Abstract: Descriptive complexity theory is a branch of complexity theory that views the hardness of a problem in terms of the complexity of expressing it in some logical formalism; among the resources considered are the number of object variables, quantifier depth, type, and alternation, sentences length (finite/infinite), etc. In this field we have studied two problems: (i) expressibility in ∃ SO and (ii) the descriptive complexity of finite abelian groups. Inspired by Fagin's result that NP = ∃SO, we have developed a partial framework to investigate expressibility inside ∃ SO so as to have a finer look into NP. The framework uses combinatorics derived from second-order Ehrenfeucht-Fraïssé games and the notion of game types. Among the results obtained is that for any k, divisibility by k is not expressible by an ∃SO sentence where (1) each second-order variable has arity at most 2, (2) the first-order part has at most 2 first-order variables, and (3) the first-order part has quantifier depth at most 3. In the second project we have investigated the descriptive complexity of finite abelian groups. Using Ehrenfeucht-Fraïssé games we find upper and lower bounds on quantifier depth, quantifier alternations, and number of variables of a first-order sentence that distinguishes two finite abelian groups. Our main results are the following. Let G1 andG2 be a pair of non-isomorphic finite abelian groups, and let m be a number that divides one of the two groups' orders. Then the following hold: (1) there exists a first-order sentence ϕ that distinguishes G1 and G2 such that ϕ is existential, has quantifier depth O(logm), and has at most 5 variables and (2) if ϕ is a sentence that distinguishes G1 and G2 then ϕ must have quantifier depth Ω(log m). In infinitary model theory we have studied abstract elementary classes. We have defined Galois types over arbitrary subsets of the monster (large enough homogeneous model), have defined a simple notion of splitting, and have proved some properties of this notion such as invariance under isomorphism, monotonicity, reflexivity, existence of non-splitting extensions.

 Advisers William Gasarch; David Kueker School UNIVERSITY OF MARYLAND, COLLEGE PARK Source DAI/B 68-07, p. , Dec 2007 Source Type Dissertation Subjects Mathematics; Computer science Publication Number 3277368
Access the complete dissertation:

» Find an electronic copy at your library.
 Use the link below to access a full citation record of this graduate work: http://gateway.proquest.com/openurl%3furl_ver=Z39.88-2004%26res_dat=xri:pqdiss%26rft_val_fmt=info:ofi/fmt:kev:mtx:dissertation%26rft_dat=xri:pqdiss:3277368 If your library subscribes to the ProQuest Dissertations & Theses (PQDT) database, you may be entitled to a free electronic version of this graduate work. If not, you will have the option to purchase one, and access a 24 page preview for free (if available).