Logical Approaches to Computational Barriers

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 valid.

websites: Arnold Beckmann | 2006-04-28 |