Computability in Europe 2006
Logical Approaches to Computational Barriers

Regular Talk:
Logical characterization of the counting hierarchy

Speaker: Juha Kontinen
Slot: Array, 10:30-10:50, col. 5


The counting hierarchy CH is the analogue of the polynomial hierarchy PH, the
building block being probabilistic polynomial time PP instead of NP. We show
that the extension of first-order logic by second-order majority quantifiers of
all arities describes exactly the problems in the counting hierarchy.
This result is based on definability results which show that using
the k-ary Majority quantifier and first-order logic, the relativized k-ary
Majority quantifier (for k>1) and the k-ary second-order existential
quantifier are uniformly expressible. This result holds on all structures,
i.e., without ordering or any numeric predicates. However, assuming ordering
and predicates for PLUS and TIMES, we get exact correspondence between the
levels C_kP of CH and sentences of quantifier-rank k, where the rank depends on
the majority quantifiers only.
We also discuss the possibility of replacing the majority quantifiers by 
general proportional quantifiers saying ``more than an
r-fraction of relations", where 0<r<1, for this result to remain

websites: Arnold Beckmann 2006-04-28