[Proof Complexity] preprint

[Michal Garlik]

Dear colleagues,

A new preprint of mine, "Ajtai's Completeness Theorem for Nonstandard
Finite Structures", is available from my web page at
http://www.karlin.mff.cuni.cz/~garlik/papers/ajtaijinak1.pdf

Any comments would be most welcome.

       Kind regards,

     Michal


Abstract:
Ajtai's generalization of Gödel's completeness theorem is a tool that
can be used to construct an extension of a given pseudo-finite
structure into a model of a given theory. The existence of such model
extensions is closely related to questions in complexity theory. In
this paper we give a new proof of Ajtai's theorem using basic
techniques of model theory.