A Homological Theory of Functions

Abstract

In computational complexity, a complexity class is given by a set of problems or functions, and a basic challenge is to show separations of complexity classes A = B especially when A is known to be a subset of B. In this paper we introduce a homological theory of functions that can be used to establish complexity separations, while also providing other interesting consequences. We propose to associate a topological space S_A to each class of functions A, such that, to separate complexity classes A B', it suffices to observe a change in "the number of holes", i.e. homology, in S_A as a subclass B of B' is added to A. In other words, if the homologies of S_A and S_A B are different, then A = B'. We develop the underlying theory of functions based on combinatorial and homological commutative algebra and Stanley-Reisner theory, and recover Minsky and Papert's 1969 result that parity cannot be computed by nonmaximal degree polynomial threshold functions. In the process, we derive a "maximal principle" for polynomial threshold functions that is used to extend this result further to arbitrary symmetric functions. A surprising coincidence is demonstrated, where the maximal dimension of "holes" in S_A upper bounds the VC dimension of A, with equality for common computational cases such as the class of polynomial threshold functions or the class of linear functionals in F_2, or common algebraic cases such as when the Stanley-Reisner ring of S_A is Cohen-Macaulay. As another interesting application of our theory, we prove a result that a priori has nothing to do with complexity separation: it characterizes when a vector subspace intersects the positive cone, in terms of homological conditions. By analogy to Farkas' result doing the same with *linear conditions*, we call our theorem the Homological Farkas Lemma.

Tasks

Reproductions