Abstract

We study the descriptive complexity of summation problems in Abelian groups and semigroups. An input to the summation problem consists of an Abelian semigroup G, explicitly represented by its multiplication table, and a subset X of G. The task is to determine the sum over all elements of X.  Ben Rossman asked, more than ten years ago, whether this can be expressed in the logic Choiceless Polynomial Time with counting (CPT). We show that the problem can be defined in fixed-point logic with counting (FPC) and hence in CPT, settling Rossman's question.  We also give a matching lower bound and show that the use of counting operators cannot be avoided: the summation problem, even over Abelian groups, cannot be defined in choiceless polynomial time without counting.

This is joint work with Faried Abu Zaid, Erich Graedel and Wied Pakusa.