An Isaac Newton Institute Programme

Logic and Algorithms

Syntactic vs. semantic approximations to logics that capture complexity classes

22nd February 2006

Author: Argimiro Arratia-Quesada (Universidad de Valladolid)


I will formulate a formal syntax of approximate formulas for the logic with counting quantifiers, SOLP, which is essentially a first order language extended with quantifiers that act upon second order variables of a given arity r, and count the fraction of elements in a subset of r-tuples of a model that satisfy a formula.

Some facts about SOLP}: (i) In the presence of a built-in (linear) order, it can describe NP-complete problems and fragments of it capture classes like P and NL; (ii) weakening the ordering relation to an almost order we can separate meaningful fragments, using a combinatorial tool suited for these languages.

The purpose of the approximate formulas is to provide a syntactic approximation to logics contained in SOLP with built-in order, that should be complementary of the semantic approximation based on almost orders, by producing approximating logics where problems are described within a small counting error. I will introduce a concept of strong expressibility based on approximate formulas, and show that for many fragments of SOLP with built-in order, including ones that capture P and NL, expressibility and strong expressibility are equivalent. I will state a Bridge Theorem that links expressibility in fragments of SOLP over almost-ordered structures to strong expressibility with respect to approximate formulas for the corresponding fragments over ordered structures. A consequence of these results is that proving inexpressibility results over fragments of SOLP with built-in order can be done by proving inexpressibility over the corresponding fragments with built-in almost order, where separation proofs are easier.