Article,
A Homological Theory of Functions
(2017)cite arxiv:1701.02302Comment: 72 pages, 22 figures. Comments welcome.
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 \not= 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 \not= 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 $\mathbb
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.
