A Homological Theory of Functions

Publication date 9 January 2017

Complexity of computation (including implicit computational complexity) (03D15) Combinatorial aspects of commutative algebra (05E40) (Co)homology of commutative rings and algebras (e.g., Hochschild, André-Quillen, cyclic, dihedral, etc.) (13D03) Applications of commutative algebra (e.g., to statistics, control theory, optimization, etc.) (13P25) Convex sets without dimension restrictions (aspects of convex geometry) (52A05) Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.) (52B40)

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 o t = 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 s u b s e t e q 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 c u p B}

are different, then

A o t = 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

m a t h b b 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.

This page was built for publication: A Homological Theory of Functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6281711)