Regular Representations of Uniform TC⁰

Abstract

In this article, we consider the interplay of generalized quantifiers and built-in relations over finite structures, in particular, in the range of logics capturing the circuit complexity classes AC0 and TC0. It is well known that for capturing AC0 first-order logic has to be equipped with order and, e.g., predicates for addition and multiplication, whereas for TC0 generalized quantifiers such as majority quantifiers are necessary. The sharp division between the classes AC0 and TC0 can be explained by the fact that AC0 is not closed under restricting AC^0-computable queries into simple subsequences of the input, whereas TC0 is closed under such relativization as its queries can be expressed in terms of first-order formulas using universe-independent generalized quantifiers and order as the only built-in relation. In the terminology of abstract logics, the above means that logics capturing AC0 do not have the relativization property, and hence, they are not regular logics unlike the logics capturing TC0. This weakness of AC0 has been also elaborated in the line of research on the Crane Beach Conjecture. The conjecture (which was refuted by Barrington et al.) was that if a language L has a neutral letter, then L can be defined in FOA, first-order logic with the collection of all numerical built-in relations A, if and only if L can be already defined in FO≤. Our approach is two-fold. First, we study universe-independent cardinality quantifiers Q defined by a parameter set S ⊆ N and formulate a combinatorial criterion for S implying that all languages in DLOGTIME-uniform TC0 can be defined in FO≤(Q). For instance, this criterion is satisfied if S is the range of some polynomial with positive integer coefficients of degree at least two. Second, by adapting the key properties of abstract logics to accommodate built-in relations, we define the regular interior R-int(L) (the largest regular L* such that L*⊆L) and regular closure R-cl(L) (the least regular L* such that ℒ⊆ℒ*), of a logic ℒ with built-in relations, and show that the Crane Beach Conjecture can be interpreted as a statement concerning the regular interior of ℒ. By extending the results of Barrington et al., we further show that if B={+}, or B contains only unary relations besides ≤, then R-int(FOℬ)≡FO≤. In contrast, our results from the first part of the article imply that if B contains ≤ and the range of a polynomial of degree at least two, then R-cl(FOB) includes all languages in DLOGTIME-uniform TC0.