Proof framework links counting to circuit and space complexity classes

Applicative theories can count

Logic in Computer Science

Summary

This paper studies how to describe different types of computer calculations using a logical framework called applicative theories. The authors create a family of such theories that can capture computations from very simple circuits to those that need a lot of memory (polynomial space). By changing a simple rule in the theories, they can describe how different kinds of counting happen in computations. This helps to better understand and separate certain complexity classes—groups that classify problems based on how hard they are to compute. They also solve an open problem by characterizing polynomial space computations within this framework.

What this means in practice

  • For complexity theorists: Use the new applicative theory characterizations to analyze relationships between complexity classes and guide further theoretical research.
  • For circuit designers: Inform design of constant-depth or logarithmic-depth Boolean circuits by understanding the theoretical limits characterized by the applicative theories.

A theory result. No direct application yet.

Authors

Melissa Antonelli, Marcel Ertel, Eduardo Skapinakis

Abstract

Applicative theories offer a proof-theoretic framework for studying complexity. In this paper, we introduce a family of applicative theories to characterize classes ranging from constant-depth circuits to polynomial space. Our approach relies on a simple axiom scheme, the small variations of which allows to capture various forms of counting and alternation. This leads to highly uniform results. When applied on notation, the scheme captures bit counting, yielding a characterization of the functions computable by constant-depth, polynomial-size threshold circuits ($\textbf{FTC}^0$); when applied lexicographically, it allows for the counting of accepting computations, yielding a characterization of the functions in the counting hierarchy ($\textbf{FCH}$). Increasing the logical complexity of the induction formulas allowed in the scheme, we obtain characterizations of the functions computable by bounded Boolean circuits of logarithmic-depth and polynomial-size ($\textbf{FNC}^1$) and of the functions computable in polynomial space ($\textbf{FPSPACE}$). The latter characterization solves an open problem in the field. Finally, we investigate separation results. While it is unknown whether $\textbf{FNC}^1$ and $\textbf{FCH}$ are different, there is an oracle relative to which (relativized) $\textbf{FNC}^1$ is strictly contained in (relativized) $\textbf{FCH}$. We use this fact to separate the theories characterizing them, by exploring their ability to represent higher-order functionals.