The INI has a new website!

This is a legacy webpage. Please visit the new site to ensure you are seeing up to date information.

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.