To access the full text documents, please follow this link:

Expressive power and complexity of a logic with quantifiers that count proportions of sets
Arratia Quesada, Argimiro Alejandro; Ortiz Gómez, Carlos
Universitat Politècnica de Catalunya. Departament de Llenguatges i Sistemes Informàtics
We present a second-order logic of proportional 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. Our logic is capable of expressing proportional versions of different problems of complexity up to NP-hard as, for example, the problem of deciding if at least a fraction 1/n of the set of vertices of a graph form a clique; and fragments within our logic capture complexity classes as NL and P, with auxiliary ordering relation. When restricted to monadic second-order variables, our logic of proportional quantifiers admits a semantic approximation based on almost linear orders, which is not as weak as other known logics with counting quantifiers (restricted to almost orders), for it does not have the bounded number of degrees property. Moreover, we show that, in this almost-ordered setting, different fragments of this logic vary in their expressive power, and show the existence of an infinite hierarchy inside our monadic language. We extend our inexpressibility result of almost-ordered structure to a fragment of SOLP, which in the presence of full order captures P. To obtain all our inexpressibility results, we developed combinatorial games appropriate for these logics, whose application could go beyond the almost-ordered models and hence are interesting by themselves.
Peer Reviewed
Àrees temàtiques de la UPC::Informàtica::Informàtica teòrica::Algorísmica i teoria de la complexitat
Computational complexity
Computer logic
Complexitat computacional
Lògica informàtica
Article - Draft

Show full item record

Related documents

Other documents of the same author

Arratia Quesada, Argimiro Alejandro; Ortiz Gómez, Carlos
Arratia Quesada, Argimiro Alejandro; Stewart, Iain A.
Arratia Quesada, Argimiro Alejandro; Stewart, Iain A.
Arratia Quesada, Argimiro Alejandro; Stewart, Iain A.