2007/01/01 by Arnaud Durand, Durand, Arnaud, Clemens Lautemann +3
Computer Science · #Complexity and Algorithms in Graphs #Computability, Logic, AI Algorithms #Graph Labeling and Dimension Problems #Small complexity classes #logic #polylog counting
paper · doi:10.4230/dagsemproc.06451.4
openalex publication_date 2007/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The counting ability of weak formalisms is of interest as a measure of their expressive power. The question was investigated in the 1980's in several papers in complexity theory and in weak arithmetic. In each case, the considered formalism (AC0--circuits, first--order logic, Delta0, respectively) was shown to be able to count precisely up to a polylogarithmic number. An essential part of each of the proofs is the construction of a 1--1 mapping from a small subset of 0,ldots,N-1 into a small initial segment. In each case the expressibility of such a mapping depends on some strong argument (group theoretic device or prime number theorem) or intricate construction. We present a coding device based on a collision-free hashing technique, leading to a completely elementary proof for the polylog counting capability of first--order logic (with built--in arithmetic), AC0--circuits, rudimentary arithmetic, the Linear Hierarchy, and monadic--second order logic with addition.