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 \subseteq 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 \cup 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.

本论文提出了一种基于同调理论的函数同之间的复杂性分离，并利用组合和同调交换代数及 Stanley-Reisner 理论发展了该基础理论，并推导出关于多项式阈值函数的最大定理，并给出了同调 Farkas 引理，以及一些关注的应用实例。