%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%  Some Dichotomy Theorems for Neural Learning Problems
%  (On methods to keep learning away from intractability,
%   International Conference on Artificial Neural Networks ICANN '95)
%
%  Michael Schmitt
%  Ruhr-Universitaet Bochum
%
%  Journal Version, June 21, 1999
%  continued January 20, 2004
%  submitted March 29, 2004: Journal of Machine Learning Research
%  final version July 14, 2004
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\documentclass[twoside,11pt]{article}

\usepackage{jmlr2e}
\usepackage{amsmath}
\usepackage{algorithm}
\usepackage{algorithmic}
\usepackage[dvips]{psfrag}

\renewcommand{\algorithmicrequire}{\textbf{Input:}}
\renewcommand{\algorithmicensure}{\textbf{Output:}}
\newcommand{\B}{{\cal B}}
\newcommand{\C}{{\cal C}}
\newcommand{\D}{{\cal D}}
\newcommand{\Coin}{\mathop{\hbox{\rm Coin}}}
\newcommand{\Sparse}{\mathop{\hbox{\rm Sparse}}}
\newcommand{\Dom}{\mathop{\hbox{\rm Dom}}}
\newcommand{\F}{{\cal F}}
\newcommand{\integers}{\mathbb{Z}}
\renewcommand{\L}{{\cal L}}
\newcommand{\naturals}{\mathbb{N}}
\newcommand{\Neg}{\mathop{\hbox{\rm Neg}}}
\newcommand{\Pos}{\mathop{\hbox{\rm Pos}}}
\newcommand{\reals}{\mathbb{R}}
\newcommand{\rplus}{\reals^+}
\newcommand{\sgn}{\mathop{\hbox{\rm sgn}}}

\jmlrheading{5}{2004}{891--912}{3/04}{8/04}{Michael Schmitt} 

\ShortHeadings{Dichotomy Theorems for Neural Learning Problems}{Schmitt} 
\firstpageno{891}

\begin{document}

\title{Some Dichotomy Theorems for Neural Learning Problems}

\author{\name Michael Schmitt \email mschmitt@lmi.ruhr-uni-bochum.de \\
       \addr Lehrstuhl Mathematik und Informatik \\
       Fakult\"{a}t f\"{u}r Mathematik \\
       Ruhr-Universit\"{a}t Bochum \\
       D--44780 Bochum, Germany}

\editor{Manfred K. Warmuth}

\maketitle

\begin{abstract}%
  The computational complexity of learning from binary examples is
  investigated for linear threshold neurons.  We introduce
  combinatorial measures that create classes of infinitely many
  learning problems with sample restrictions.  We analyze how the
  complexity of these problems depends on the values for the measures.
  The results are established as dichotomy theorems showing that each
  problem is either NP-complete or solvable in polynomial time.  In
  particular, we consider consistency and maximum consistency problems
  for neurons with binary weights, and maximum consistency problems
  for neurons with arbitrary weights. We determine for each problem
  class the dividing line between the NP-complete and polynomial-time
  solvable problems. Moreover, all efficiently solvable problems are
  shown to have constructive algorithms that require no more than
  linear time on a random access machine model.  Similar dichotomies
  are exhibited for neurons with bounded threshold.  The results
  demonstrate on the one hand that the consideration of sample
  constraints can lead to the discovery of new efficient algorithms
  for non-trivial learning problems. On the other hand, hard learning
  problems may remain intractable even for severely restricted
  samples.
\end{abstract}

\begin{keywords} 
  linear threshold neuron, consistency problem, computational
  complexity, linear-time algorithm, NP-completeness
\end{keywords}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Introduction}
\label{sec:introduction}

% consistency problems

The ability to learn is certainly one of the most challenging
qualities that people have ever demanded from computers.  There is no
doubt that a major advancement in the development of learning
algorithms has been made due to the use of neural networks.  Today,
they provide the basis for some of the most successful learning
techniques.  This achievement, however, is compromised by the fact
that the running times required by neural learning algorithms are
often immense. On the theoretical side, investigations of the
computational complexity of learning problems have supported the
conjecture that neural learning is generally hard: Theory considers an
algorithm as efficient if its running time is bounded by a polynomial
in the input length. Based on the theory of NP-completeness \cite[see,
e.g.,][]{GareyJohnson:79} researchers have established numerous
intractability results for neural learning problems. Consequently, no
efficient, that is, polynomial-time, algorithm for solving these
problems can exist if the complexity classes P and NP are different.
\cite[See, e.g.,][for a comprehensive list of hardness results
concerning single neurons and neural networks.]{Sima:02}

A useful approach for studying the complexity of learning is to
consider the consistency problem. Associated with a class of
functions, the so-called hypothesis class, the consistency problem is
a decision problem. It poses the question whether for a given set of
labeled examples, the training sample, there is some hypothesis in the
class that is consistent with all examples, that is, assigns the
correct output values. The consistency problem is also known as
loading problem \cite[]{Judd:90}, fitting problem
\cite[]{Natarajan:91}, or training problem \cite[]{BlumRivest:92}. A
variant of the consistency problem is the maximum consistency problem,
also known as minimizing disagreement problem. Its instances consist
of a training sample and a natural number $k$. The question is to
decide whether there is a hypothesis consistent with some subset of at
least $k$ examples.  The maximum consistency problem is a
generalization of the consistency problem in that the latter is a
subproblem of the former: The consistency problem can be obtained from
the maximum consistency problem by setting $k$ equal to the number of
examples. Consequently, if for a given hypothesis class the
consistency problem is NP-hard then the maximum consistency problem is
NP-hard, too. Consistency and maximum consistency problems are studied
as key problems in the computational models of learning known as
probably approximately correct (PAC) learning and agnostic PAC
learning. A fundamental result states that, under the assumption that
the complexity classes RP and NP are different, PAC learning cannot be
efficient for a hypothesis class if the consistency problem for this
class is NP-hard \cite[]{PittValiant:88,BlumerEhrenfeuchtHW:89}. An
analogous result links the model of agnostic PAC learning with the
maximum consistency problem
\cite[]{KearnsSchapireS:94,AnthonyBartlett:99}.

%%% single neurons

There has been perseverating interest in theoretical issues of
learning using single neurons as hypothesis class \cite[see,
e.g.,][and the references there]{Servedio:02}. One of the extensively
studied models is the linear threshold neuron, also known as
McCulloch-Pitts neuron \cite[]{McCullochPitts:43}. It serves as
elementary building block for many neural network types \cite[see,
e.g.,][]{Haykin:99}. While the linear threshold neuron has arbitrary
real-valued weights, a variant that has gained particular attention is
obtained by restricting the weights to binary values \cite[see,
e.g.,][]{GoleaMarchand:93,FangVenkatesh:96,KimRoche:98,SommerPalm:99}.
With binary weights a linear threshold neuron is still able to compute
fundamental Boolean functions such as conjunction, disjunction, and
$r$-of-$k$ threshold functions\footnote{A Boolean $r$-of-$k$ threshold
  function outputs $1$ if and only if at least $r$ in a specified
  subset of $k$ variables have the value $1$.} that have been of
specific interest in questions of learning
\cite[]{HampsonVolper:86,Littlestone:88,PittValiant:88}.

In this article, we investigate the complexity of consistency and
maximum consistency problems for linear threshold neurons with binary
and with arbitrary weights. We do this under the assumption that the
training examples are binary, that is, have entries from $\{0,1\}$.
While the consistency problem for linear threshold neurons with
arbitrary weights is known to be solvable in polynomial time using
methods of linear programming \cite[see,
e.g.,][]{MaassTuran:94,AnthonyBartlett:99} we focus on those problems
that are NP-complete: The consistency problem for linear threshold
neurons with binary weights has been proved to be NP-complete by
\cite{PittValiant:88}. Hence, also the maximum consistency problem for
these neurons is NP-complete. The maximum consistency problem for
linear threshold neurons with arbitrary weights is known to be
NP-complete from the work of \cite{HoeffgenSimonvH:95} improving an
earlier result by \cite{Amaldi:91}.

We take a closer look at these problems by introducing and analyzing
subproblems. In other words, we raise the question whether these
problems become easier when the training samples are restricted.  To
this end we define two combinatorial measures for characterizing the
complexity of a sample.  The first quantity, called coincidence,
indicates the maximum number of components in which any two examples
are both non-zero.  The second measure, called sparseness, represents
the maximum number of non-zero components, or the Hamming-weight, of
any example. The choice of these measures is guided by the insight
that learning for single neurons is easy when the coincidence or the
sparseness of the samples is severely limited. So, it is not hard to
see that the consistency problem is trivial when the examples are
pairwise orthogonal, that is, when the sample has coincidence zero.
The same observation can be made for the case when the examples are
required to be extremely sparse. A further motivation for introducing
sparseness arises from investigations of neural associative memories.
In these, sparseness has been shown to be relevant for their storage
capacities using specific learning rules \cite[]{Palm:80}.

% dichotomy theorems

By introducing coincidence and sparseness as sample restrictions we
obtain infinite classes of consistency and maximum consistency
problems: For each pair $c,d$ of natural numbers there is the
(maximum) consistency problem with coincidence $c$ and sparseness $d$.
The question arises how the complexity of the consistency and the
maximum consistency problems depends on the values for coincidence and
sparseness. As one of the main results it emerges that these problems
are already NP-complete when coincidence and sparseness are bounded, a
fact that does not follow from previous work. Moreover, we give a
complete categorization of these consistency and maximum consistency
problems into NP-complete and polynomial-time solvable. In other
words, we establish so-called dichotomy theorems for these problems.
Given an infinite class of problems, a dichotomy theorem states that
each problem is either NP-complete or contained in the complexity
class P.  Thus, if P $\neq$ NP, the dichotomy theorem separates the
efficiently solvable problems from the intractable ones. A dichotomy
theorem is an important finding since it is known that if P and NP are
different then there are infinitely many problems in NP that are
neither in P nor NP-complete \cite[see, e.g.,][]{GareyJohnson:79}. It
is therefore significant that none of these problems of intermediate
complexity is found among the (maximum) consistency problems
considered here. In computational complexity there are only a few
dichotomy theorems known. The most popular one is that for $k$-SAT
which states that the satisfiability problem for conjunctions of
Boolean clauses, where each clause has size at most $k$, is
NP-complete when $k$ is at least $3$ and solvable in polynomial time
for $k$ at most $2$. The dichotomy of $k$-SAT emerges as a special
case of the renowned result of \cite{Schaefer:78} who established a
more general dichotomy theorem for satisfiability problems. Concerning
more recent results we refer to \cite{KirousisKolaitis:03} where also
a brief survey on dichotomy theorems in computational complexity is
given.  The first dichotomy theorem in conjunction with learning
problems has been provided by \cite{Dalmau:99} for learning quantified
Boolean formulas \cite[see also][]{DalmauJeavons:03}.

In detail, we prove the following dichotomy theorems: The consistency
problem for the linear threshold neuron with binary weights is
NP-complete if the samples have coincidence at least $1$ and
sparseness at least $4$. On the other hand, if the samples have
coincidence $0$ or sparseness at most $3$, the problem becomes
solvable in polynomial time. Further, the maximum consistency problem
for the linear threshold neuron with binary weights is NP-complete for
coincidence at least $1$ and sparseness at least $2$, whereas for
coincidence $0$ or sparseness $1$ it is in P. This last dichotomy
theorem holds also for the maximum consistency problem with respect to
the linear threshold neuron with arbitrary weights.  All
polynomial-time results are established by showing that the problems
can be solved in linear time on a random access machine (RAM) model.
Moreover, the algorithms we present for these problems are
constructive, that is, they calculate a solution if one exists.  We
further obtain dichotomies for linear threshold neurons with binary
weights and a bounded threshold.  In particular, the dichotomy of the
consistency problems that holds for these neurons with arbitrary
threshold is also existent when the threshold is bounded by some value
larger than or equal to $2$. On the other hand, if the bound on the
threshold is at most $1$, the consistency problem is solvable in
linear time on a RAM. For the maximum consistency problem and linear
threshold neurons with binary weights NP-completeness is found at a
value for the threshold of $1$ or greater, whereas linear-time
solvability holds when the threshold is equal to $0$.

The dichotomy theorems presented here extend the NP-completeness
results for learning with single neurons to an infinite class of
subproblems. Therefore, they confirm that neural learning belongs to
the hardest computational problems that one needs to solve in
practice.  On the other hand, those problems that we find to be
solvable in polynomial time can be solved even in linear time on a
RAM. The algorithms designed for these problems give interesting new
insights. Moreover, efficiently solvable subproblems have been
successfully used for the design of improved heuristics for
NP-complete problems \cite[]{ZhengStuckey:02}.  Therefore, it is
reasonable to expect that the new linear-time algorithms presented
here may lead to new and faster heuristics for learning in single
neurons and neural networks.

% overview

In Section~\ref{sec:definitions} we introduce the definitions of the
basic concepts. The dichotomy theorems are stated in
Section~\ref{sec:dichotomytheorems}.  The proofs are given in the
following two sections: Section~\ref{sec:npcomplete} is concerned with
the NP-completeness results while the linear-time algorithms are
presented in Section~\ref{sec:lineartimealgorithms}.
Section~\ref{sec:conclusions} is devoted to some conclusions and open
questions.  In the appendix we establish the NP-completeness of a new
variant of the satisfiability problem that is used in
Section~\ref{sec:npcomplete}.  We assume that the reader is familiar
with the theory of NP-completeness as covered, for instance, by
\cite{GareyJohnson:79}.

{\bf Bibliographic Note.} Some of the results in this article have
been previously described in a technical report \cite[]{94a:Schmitt}
and presented at the International Conference on Artificial Neural
Networks, ICANN '95, in Paris \cite[]{95c:Schmitt}. This article is a
thoroughly revised and extended version of these papers.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Neurons, Samples, Problems, and Algorithms}
\label{sec:definitions}

We begin by defining the neuron model and the function classes
associated with it.  Then we introduce the notion of a sample and
specify the computational problems involved with neurons and samples.
Finally, with regard to the linear-time algorithms presented in
Section~\ref{sec:lineartimealgorithms}, we describe the computer model
of the random access machine (RAM) on which the time bounds rely.

%%%%%%%%%%%%%%%%%%%%
\subsection{Neurons}
\label{subsec:neurons}

A linear threshold neuron has parameters $w_1,\dots,w_n,t\in\reals$,
where $w_1,\dots,w_n$ are the weights and $t$ is the threshold. The
class of linearly separable Boolean functions in $n$ variables,
denoted $\L_n$, is the class of functions
$f:\{0,1\}^n\rightarrow\{0,1\}$ that can be computed by a linear
threshold neuron. Specifically, for every $f\in\L_n $ there are
weights $w_1,\dots,w_n$ and a threshold $t$ such that for all
$x\in\{0,1\}^n$,
\begin{eqnarray*}
f(x) & = &  \left\{\begin{array}{ll}
1 & \text{if }  w_1x_1+\dots+w_nx_n\geq t, \\
0 & \text{otherwise}.
\end{array}\right.
\end{eqnarray*}

We use $\B_n$ to denote the subclass of linearly separable Boolean
functions in $n$ variables that can be computed by a linear threshold
neuron using only binary weights, that is, $w_1,\dots,w_n\in\{0,1\}$.
Further, $\B_n^\ell$ is the subclass of functions in $\B_n$ that can
be computed with threshold $t\leq \ell$. Clearly, a value of
$\ell\in\{0,\dots,n\}$ is sufficient and we have $\B_n^n=\B_n$.

By omitting the subscript $n$ we refer to the union of the respective
classes such as, for instance, $\L=\bigcup_{n\geq 1}\L_n$.

%%%%%%%%%%%%%%%%%%%%%
\subsection{Samples}
\label{subsec:samples}

A sample $S$ is a finite set $S\subseteq\{0,1\}^n\times \{0,1\}$. The
elements of $S$ are called examples. Given a sample $S$, the set of
positive examples $\Pos(S)$ and the set of negative examples $\Neg(S)$
of $S$ are defined by
\begin{eqnarray*}
\Pos(S) & = & \{x \mid (x,1)\in S\},\\
\Neg(S) & = & \{x \mid (x,0)\in S\}.
\end{eqnarray*}
A sample may contain examples that are both positive and negative.
Otherwise, that is, if $\Pos(S)\cap\Neg(S)=\emptyset$, the sample is
said to be consistent.\footnote{The term ``consistent sample'' uses the
  word ``consistent'' in a somewhat different sense than the rest of
  the article.}  The domain of a sample $S$, denoted $\Dom(S)$, is
the set
\begin{eqnarray*}
\Dom(S) & = & \Pos(S)\cup\Neg(S).
\end{eqnarray*}

We introduce two combinatorial measures that assign natural numbers to
samples: coincidence and sparseness. The coincidence of a sample $S$,
denoted $\Coin(S)$, is
\begin{eqnarray*}
\Coin(S) & = & \left\{\begin{array}{ll}
\max\{x\cdot y \mid x,y\in \Dom(S),\;x\neq y\} & \text{if }|S|\geq 2,\\
0 & \text{otherwise}, \end{array}\right.
\end{eqnarray*}
where $x\cdot y$ denotes the inner product. The sparseness of $S$,
$\Sparse(S)$, is
\begin{eqnarray*}
\Sparse(S) & = & \left\{\begin{array}{ll}
\max\{x\cdot x \mid x\in \Dom(S)\} & \text{if } S\neq\emptyset, \\
0 & \text{otherwise}. \end{array}\right.
\end{eqnarray*}
Thus, $\Coin(S)$ is the maximum number of components in which two
different elements in the domain of $S$ have a $1$ in common, and
$\Sparse(S)$ is the maximum number of $1$s, or the Hamming weight, of
an element. Note that $\Coin(S)\leq\Sparse(S)$. Thus, bounding the
sparseness of samples by some constant also bounds their coincidence
by the same constant.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Consistency Problems}
\label{subsec:problems}

Given a sample $S$, a function $f$ is said to be consistent with $S$
if $f$ satisfies $f(x)=a$ for all $(x,a)\in S$. The consistency
problem for a class $\F$ of Boolean functions is the problem to decide
whether for an input sample $S$ there exists some function $f\in\F$
that is consistent with $S$. Loading problem, fitting problem, and
training problem are synonyms for the consistency problem.

Let $\F$ be a class of Boolean functions and let $c,d\in\naturals$.
We define the following consistency problems for $\F$ with sample
restrictions:
\begin{quote}
\begin{tabbing}
{\sc $\F$-Consistency with Coincidence $c$} \\
Question: \=Is \kill
Instance: \>A sample $S$ with $\Coin(S)\leq c$.\\
Question: \>Is there a function $f\in\F$ that is consistent with $S$?
\end{tabbing}

\begin{tabbing}
{\sc $\F$-Consistency with Sparseness $d$}\\
Question: \=Is \kill
Instance: \>A sample $S$ with $\Sparse(S)\leq d$.\\
Question: \>Is there a function $f\in\F$ that is consistent with $S$?
\end{tabbing}
\end{quote}
The definition of the problem {\sc $\F$-Consistency with Coincidence
  $c$ and Sparseness $d$} is similar.

The instances of the maximum consistency problem for a class ${\cal
  F}$ of functions consist of a sample $S$ and a number
$k\in\naturals$. The question is whether there exists a subset of $S$
with at least $k$ elements and a function $f\in{\cal F}$ consistent
with that subset.  Given numbers $c,d\in\naturals$, we define maximum
consistency problems for $\F$ with sample restrictions as follows:
\begin{quote}
\begin{tabbing}
{\sc Max-$\F$-Consistency with Coincidence $c$} \\
Question: \=Is \kill
Instance: \>A sample $S$ with $\Coin(S)\leq c$ and a natural number $k$.\\
Question: \>\parbox[t]{10.5cm}{Is there a subsample $S^\prime\subseteq S$ with
$|S^\prime|\geq k$ and a function $f\in\F$ that is consistent with 
$S^\prime$?}
\end{tabbing}

\begin{tabbing}
{\sc Max-$\F$-Consistency with Sparseness $d$} \\
Question: \=Is \kill
Instance: \>A sample $S$ with $\Sparse(S)\leq d$ and a natural number $k$.\\
Question: \>\parbox[t]{10.5cm}{Is there a subsample $S^\prime\subseteq S$ with
$|S^\prime|\geq k$ and a function $f\in\F$ that is consistent with 
$S^\prime$?}
\end{tabbing}
\end{quote}
Further, we consider the problem called {\sc Max-$\F$-Consistency with
  Coincidence $c$ and Sparseness $d$}, which is the problem where the
instances satisfy both constraints.

There are some natural relationships among the complexities of these
problems. Clearly, an algorithm that solves the consistency problem
with sparseness $d$ solves also every consistency problem with
sparseness less than $d$ for the same function class. Furthermore, if
the consistency problem is shown to be NP-hard for some sparseness $d$
then it follows that all consistency problems with sparseness larger
than $d$ for the same function class are NP-hard as well, since the
reduction established for sparseness $d$ is also valid for larger
bounds on the sparseness.

Similar considerations can be made with regard to coincidence.
Moreover, complexity results for consistency problems with bounded
coincidence have consequences for the complexity of consistency
problems with bounded sparseness, and vice versa. In particular, an
algorithm that solves the consistency problem for coincidence $c$
solves also the consistency problem for sparseness $c+1$ since every
sample with sparseness at most $c+1$ has coincidence no more than $c$.
(Note that coincidence is measured using non-identical pairs only.)
Correspondingly, NP-hardness for sparseness $d$ implies NP-hardness
for coincidence $d-1$.

Analogous interdependences hold among the maximum consistency problems
with sample restrictions. Additionally, maximum consistency problems
are related to consistency problems in that the consistency problem is
a subproblem of the corresponding maximum consistency problem. The
former is obtained from the latter by letting the number $k$ be equal
to the cardinality of the sample.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Linear-Time Algorithms}
\label{sec:lineartime}

We give linear-time algorithms for all problems not shown to be
NP-complete. While the complexity class P is known to be widely
machine independent, this is not the case for the class of problems
solved in linear time on some machine. In fact, a detailed account of
the computer model must be given. We adopt the model of a random
access machine (RAM) as it is the most realistic formal computer model
and frequently used when analyzing the running time of algorithms
\cite[see, e.g.,][]{vanEmdeBoas:90}. The instruction set of the RAM
model comprises the standard load and store operations including the
use of indirect addresses. Its arithmetic operations are addition and
subtraction, whereas multiplication and division are not available. We
give time bounds for RAMs in the uniform measure, that is, the
execution of an instruction counts as one unit of time. It is known
that every RAM that requires time $t(n)$ in the uniform measure can be
simulated on a multi-tape Turing machine in time $O(t^3(n))$
\cite[]{CookReckhow:73}. In particular, a linear-time algorithm on a
RAM ensures that the problem it solves belongs to P.



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Dichotomy Theorems}
\label{sec:dichotomytheorems}

We present five dichotomy theorems about the complexity of consistency
problems with sample restrictions. They deal with the function classes
$\B,\B^\ell$, and $\L$ introduced in Section~\ref{subsec:neurons} and
the consistency problems and maximum consistency problems with sample
restrictions defined in Section~\ref{subsec:problems}. The dichotomy
theorems establish that, with one exception, each of these problems is
either NP-complete or solvable in polynomial time. The latter is shown
by exhibiting linear-time algorithms in all cases. The exception is
the problem class arising from {\sc $\L$-Consistency}. All subproblems
of {\sc $\L$-Consistency} can be solved in polynomial time as {\sc
  $\L$-Consistency} itself is solvable in polynomial time using linear
programming \cite[see, e.g.,][]{AnthonyBartlett:99,MaassTuran:94}.
Therefore, if P $\neq$ NP, none of the subproblems of {\sc
  $\L$-Consistency} is NP-complete.

The proofs for the statements that claim NP-completeness are presented
in Section~\ref{sec:npcomplete}. The linear time bounds are
established in Section~\ref{sec:lineartimealgorithms} by giving
algorithms that solve the problems constructively, that is, provide a
solution if there exists one.

The first dichotomy theorem is concerned with the consistency problem
for neurons with binary weights and arbitrary threshold.

\begin{theorem}
\label{thm:consb}
{\sc $\B$-Consistency with Coincidence $c$ and Sparseness $d$} is
NP-complete whenever $c\geq 1$ and $d\geq 4$. On the other hand, {\sc
  $\B$-Consistency with Coincidence $0$} and {\sc $\B$-Consistency
  with Sparseness $d$} for $d\leq 3$ is solvable in linear time.
\end{theorem}

An analogous result holds for neurons where the threshold is bounded
by a constant of value at least $2$. Moreover, if the threshold is
required to be at most $1$, we obtain solvability in linear time for
all values of coincidence and sparseness.

\begin{theorem}
\label{thm:consbl}
For every $\ell\geq 2$, Theorem~\ref{thm:consb} holds with $\B^\ell$ in place
of $\B$. On the other hand, {\sc $\B^1$-Consistency with Coincidence
  $c$} and {\sc $\B^1$-Consistency with Sparseness $d$} is solvable in
linear time for all $c$ and $d$.
\end{theorem}

These statements are complemented by the following two theorems that
consider the corresponding maximum consistency problems.

\begin{theorem}
\label{thm:maxconsb}
{\sc Max-$\B$-Consistency with Coincidence $c$ and Sparse\-ness $d$}
is NP-complete whenever $c\geq 1$ and $d\geq 2$.  On the other hand,
{\sc Max-$\B$-Consistency with Coincidence $0$} and {\sc
  Max-$\B$-Consistency with Spar\-seness $d$} for $d\leq 1$ is
solvable in linear time.
\end{theorem}

A corresponding result for neurons with bounded threshold is the
following one.

\begin{theorem}
\label{thm:maxconsbl}
For every $\ell\geq 1$, Theorem~\ref{thm:maxconsb} holds with
$\B^\ell$ in place of $\B$. On the other hand, {\sc
  Max-$\B^0$-Consistency with Coincidence $c$} and {\sc
  Max-$\B^0$-Consistency with Sparseness $d$} is solvable in linear
time for all $c$ and $d$.
\end{theorem}

Finally, we present a dichotomy theorem for maximum consistency
problems regarding neurons with arbitrary weights.

\begin{theorem}
  \label{thm:maxconsl} 
  {\sc Max-$\L$-Consistency with Coincidence $c$ and Sparseness $d$}
  is NP-complete whenever $c\geq 1$ and $d\geq 2$. On the other hand,
  {\sc Max-$\L$-Consistency with Coincidence $0$} and {\sc
    Max-$\L$-Consistency with Spar\-seness $d$} for $d\leq 1$ is
  solvable in linear time.
\end{theorem}

\begin{figure}[t]
  \begin{center}
    \psfrag{0}[][]{$0$}
    \psfrag{1}[][]{$1$}
    \psfrag{2}[][]{$2$}
    \psfrag{3}[][]{$3$}
    \psfrag{4}[][]{$4$}
    \psfrag{5}[][]{$5$}
    \psfrag{6}[][]{$6$}
    \psfrag{7}[][]{$7$}
    \psfrag{c}[][]{$c$}
    \psfrag{d}[][]{$d$}
    \psfrag{(a)}[][]{\sf (a)}
    \psfrag{(b)}[][]{\sf (b)}
    \psfrag{v}[][]{$\vdots$}
    \psfrag{h}[][]{$\cdots$}
    \psfrag{NP-complete}[][]{\large\sf NP-complete}
    \psfrag{linear time}[][]{\large\sf linear time}
    \epsfig{figure=dichofigure.eps,scale=0.7} 
    \vspace{5mm}
    \caption{The dichotomies of the consistency and maximum consistency
      problems with coincidence $c$ and sparseness $d$: {\bf (a)}
      Consistency problems for the classes $\B$ and $\B^\ell$, where
      $\ell\geq 2$ (see Theorems~\protect\ref{thm:consb}
      and~\protect\ref{thm:consbl}); {\bf (b)} maximum consistency
      problems for $\B,\B^\ell$, where $\ell\geq 1$, and $\L$ (see
      Theorems~\protect\ref{thm:maxconsb},
      \protect\ref{thm:maxconsbl}, and~\protect\ref{thm:maxconsl}).
      Linear time refers to the computing time required on a RAM model
      with uniform measure (see Section~\ref{sec:lineartime}).}
      \label{fig:dichofigure}
  \end{center}
\end{figure}

The dichotomy theorems are illustrated in
Figure~\ref{fig:dichofigure}. The dot with coordinates $(c,d)$
represents the consistency problem or the maximum consistency problem,
respectively, with coincidence $c$ and sparseness $d$.  Note that for
$c\geq d$ the problem at coordinate $(c,d)$ can be identified with the
problem at $(d-1,d)$ (see the discussion at the end of
Section~\ref{subsec:problems}). Problems with sparseness $0$ are
omitted as they are trivial.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{NP-Complete Problems}
\label{sec:npcomplete}

We establish the NP-completeness for the consistency problems of
Theorems~\ref{thm:consb} and~\ref{thm:consbl} in
Section~\ref{subsec:npconsistency}. Section~\ref{subsec:npmaximum}
deals with the maximum consistency problems of
Theorems~\ref{thm:maxconsb}, \ref{thm:maxconsbl},
and~\ref{thm:maxconsl}. In all cases it is sufficient to prove
NP-hardness since membership in NP is easy to derive: Guessing the
weights and the threshold and checking consistency or maximum
consistency for the given function classes can be done in polynomial
time.\footnote{For the function class $\L$ one makes use of the fact
  that on binary inputs a linear threshold neuron with arbitrary
  weights needs no more than polynomially in $n$ many bits to
  represent weights and threshold \cite[see, e.g.,][]{94b:Schmitt}.}

%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Consistency}
\label{subsec:npconsistency}

The problem {\sc $\B$-Consistency} without sample restrictions was
shown to be NP-complete by \cite{PittValiant:88}. They have defined a
reduction from the problem {\sc Zero-One Integer Programming} that
uses samples of unbounded coincidence and, hence, unbounded sparseness.
To prove the stronger result, we make a new approach and establish a
reduction from a problem that is a variant of the satisfiability
problem which we call {\sc Almost Disjoint Positive 1-in-3Sat}.
\begin{quote}
\begin{tabbing}
{\sc Almost Disjoint Positive 1-in-3Sat}\\
Question: \=Is \kill
Instance: \>\parbox[t]{10.5cm}{A set $U$ of variables, a collection 
  $\C$ of subsets of $U$ such that each subset $C\in\C$ 
  has exactly three elements and each pair of subsets $C,D\in\C, 
  C\neq D$, satisfies $|C\cap D|\leq 1$.}\\[.5mm]
Question: \>\parbox[t]{10.5cm}{Is there a truth assignment
  $\alpha:U\rightarrow\{0,1\}$ such that each subset in $\C$ has
  exactly one true variable?}
\end{tabbing}
\end{quote}
The attribute ``positive'' refers to the fact that the variables are
not negated; ``almost disjoint'' means that two subsets have at most
one variable in common. The problem {\sc Positive 1-in-3Sat} is known
to be NP-complete \cite[][p.~259]{GareyJohnson:79}. That the
subproblem is NP-complete as well is claimed by the following
statement. Its proof is given in the appendix.

\begin{lemma}
\label{lem:1in3sat}
{\sc Almost Disjoint Positive 1-in-3Sat} is NP-complete.
\end{lemma}

This fact is employed in the following result. It covers the
NP-completeness part of in Theorem~\ref{thm:consb}. (Note that, as was
argued in Section~\ref{subsec:problems}, NP-hardness of the
consistency problem with coincidence $c$ and sparseness $d$ implies
NP-hardness for any coincidence $c'\geq c$ and sparseness $d'\geq d$.)

\begin{theorem}
\label{thm:consbnp}
{\sc $\B$-Consistency with Coincidence 1 and Sparseness 4} is
NP-complete.
\end{theorem}

\begin{proof}
  The proof is by reduction from the problem {\sc Almost Disjoint
    Positive 1-in-3Sat} defined above. Assume that an instance of this
  problem is given by the set of variables $U=\{u_1,\dots,u_n\}$ and
  the collection of subsets $\C=\{c_1,\dots,c_m\}$. The reduction maps
  this instance to a sample $S\subseteq\{0,1\}^{4n+m+2}\times\{0,1\}$.
  We introduce the following notation: Given a set
  $\{i_1,\dots,i_j\}\subseteq\{1,\dots,k\}$, let $[i_1,\dots,i_j]_k$
  denote that element of $\{0,1\}^k$ which has a $1$ in positions
  $i_1,\dots,i_j$, and $0$ elsewhere. Then $S$ is constructed as
  follows: For each variable $u_i\in U$, we define four examples
  \begin{eqnarray}
  [i,n+i]_{4n+m+2}           & \in & \Neg(S), \label{Abin1}\\[0mm]
  [2n+i,3n+i]_{4n+m+2}       & \in & \Neg(S), \label{Abin2}\\[0mm]
  [i,3n+i,4n+m+2]_{4n+m+2}   & \in & \Pos(S), \label{Abin3}\\[0mm]
  [n+i,2n+i,4n+m+2]_{4n+m+2} & \in & \Pos(S). \label{Abin4}
  \end{eqnarray}
  Each subset $c_\ell=\{u_i,u_j,u_k\}\in\C$ gives rise to three
  examples
  \begin{eqnarray}
  [i,j,k,4n+\ell]_{4n+m+2}  & \in & \Pos(S), \label{Abin5}\\[0mm]
  [n+i,n+j,n+k]_{4n+m+2}    & \in & \Pos(S), \label{Abin6}\\[0mm]
  [4n+\ell,4n+m+2]_{4n+m+2} & \in & \Pos(S). \label{Abin6a}
  \end{eqnarray}
  Finally, we add the three examples
  \begin{eqnarray}
  [4n+m+1]_{4n+m+2}        & \in & \Neg(S), \label{Abin8}\\[0mm]
  [4n+m+2]_{4n+m+2}        & \in & \Neg(S), \label{Abin9}\\[0mm]
  [4n+m+1,4n+m+2]_{4n+m+2} & \in & \Pos(S). \label{Abin7}
  \end{eqnarray}
  Obviously, $S$ can be computed from $U$ and $\C$ in polynomial time.
  Further, as can easily be checked, we have $\Coin(S)\leq 1$ and
  $\Sparse(S)\leq 4$. (Note that every pair of different subsets in
  $\C$ has at most one common variable. Hence, the examples
  in~(\ref{Abin5}) and~(\ref{Abin6}) that arise from different subsets
  have coincidence at most $1$.)
  
  It remains to show that the reduction is correct, that is, that $\C$
  has a truth assignment with exactly one true variable in each subset
  if and only if there exists a function in $\B_{4n+m+2}$ that is
  consistent with $S$.  In order to prove the ``only if'' part, assume
  that $\alpha:U\rightarrow\{0,1\}$ is a truth assignment that
  satisfies the assumption. Define the weights $w_1,\dots,w_{4n}$ as
  follows: For $i=1,\dots,n$, let
  \begin{equation*}
    \begin{array}{rclcl}
    w_i     & = & w_{2n+i} & = & \alpha(u_i),\\
    w_{n+i} & = & w_{3n+i} & = & 1-\alpha(u_i).
    \end{array}
  \end{equation*}
  The remaining weights and the threshold are determined by
  \begin{equation*}
    w_{4n+1} = \dots = w_{4n+m+2} = 1 \quad\text{and}\quad t = 2.
  \end{equation*}
  The representation of the truth assignment by the weights is shown
  in Table~\ref{tab:weights}.  Using the fact that $\alpha$ assigns
  exactly one $1$ to each subset in $\C$, it is easy to verify that
  the function represented by these parameter values is consistent
  with $S$.

  \begin{table}[t]
    \begin{center}
      \begin{tabular}[c]{|c|c|}
        \hline
          Position $i$ & Value of $w_i$ \\ \hline\hline
          $1,\dots,n$ & $\alpha(u_i)$ \\\hline
          $n+1,\dots,2n$ & $1-\alpha(u_i)$ \\\hline
          $2n+1,\dots,3n$ & $\alpha(u_i)$ \\\hline
          $3n+1,\dots,4n$ & $1-\alpha(u_i)$ \\\hline
          $4n+1,\dots,4n+m$ & $1$ \\\hline
          $4n+m+1$ & $1$ \\\hline
          $4n+m+2$ & $1$ \\ \hline
      \end{tabular}
      \caption{Definition of the weights for a given truth assignment
        $\alpha$.}
      \label{tab:weights}
    \end{center}
  \end{table}
  
  For establishing the ``if'' part, let the weights
  $w_1,\dots,w_{4n+m+2}\in\{0,1\}$ and the threshold $t$ represent a
  function that is consistent with $S$. The examples in~(\ref{Abin8}),
  (\ref{Abin9}), and (\ref{Abin7}) imply that
  \begin{eqnarray*}
  w_{4n+m+1}              & <    & t,\\
  w_{4n+m+2}              & <    & t,\\
  w_{4n+m+1} + w_{4n+m+2} & \geq & t,
  \end{eqnarray*}
  from which it follows that $w_{4n+m+1}=1$ and $w_{4n+m+2}=1$.
  Hence, the threshold satisfies $1<t\leq 2$, and we may assume
  without loss of generality that $t=2$. Then the examples
  in~(\ref{Abin6a}) entail that $w_{4n+1}=\dots =w_{4n+m}=1$.  {From}
  the examples in~(\ref{Abin1}) to (\ref{Abin4}) and the facts that
  $w_{4n+m+2}=1$ and $t=2$, we derive the inequalities
  \begin{eqnarray*}
  w_i + w_{n+i}         & \leq & 1, \\
  w_{2n+i} + w_{3n+i}   & \leq & 1, \\
  w_i + w_{3n+i} & \geq & 1, \\
  w_{n+i} + w_{2n+i}    & \geq & 1,
  \end{eqnarray*}
  for $i=1,\dots,n$. These imply the equalities
  \begin{eqnarray}
  \label{wiwnieq}
  w_{i} + w_{n+i} & = & 1,
  \end{eqnarray}
  for $i=1,\dots,n$. We define the truth assignment
  $\alpha:U\rightarrow\{0,1\}$ by
  \begin{eqnarray*}
  \alpha(u_{i}) & = & w_{i},
  \end{eqnarray*}
  for $i=1,\dots,n$. The examples in~(\ref{Abin5}), (\ref{Abin6}) and
  the fact that $t=2$ yield the inequalities
  \begin{eqnarray*}
    w_i + w_j + w_k + w_{4n+\ell} & \geq & 2, \\
    w_{n+i} + w_{n+j} + w_{n+k} & \geq & 2,
  \end{eqnarray*}
  for each subset $c_\ell=\{u_{i},u_{j},u_{k}\}\in\C$. {From} these,
  the fact that $w_{4n+1}=\dots=w_{4n+m}=1$, and the
  equations~(\ref{wiwnieq}) we get that $c_\ell$ satisfies
  \begin{eqnarray*}
    \alpha(u_{i})+\alpha(u_{j})+\alpha(u_{k}) & = & 1.
  \end{eqnarray*}
  Thus, each subset in $\C$ has exactly one $1$ assigned by $\alpha$.
  This completes the correctness proof for the reduction.
\end{proof}

The foregoing proof shows that the same reduction can be used whenever
the threshold is allowed to take on the value $2$. Thus, it follows
that the problems in Theorem~\ref{thm:consbnp} are NP-complete also
for neurons with threshold at most $\ell$, where $\ell\geq 2$. This
observation establishes the NP-completeness statement of
Theorem~\ref{thm:consbl}.

\begin{corollary}
\label{cor:consbknp}
For every $\ell\geq 2$, {\sc $\B^\ell$-Consistency with Coincidence
  $1$ and Sparseness $4$} is NP-complete.
\end{corollary}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Maximum Consistency}
\label{subsec:npmaximum}

Now, we address the NP-completeness of the maximum consistency
problems. The following result covers the intractability part of
Theorem~\ref{thm:maxconsb}.

\begin{theorem}
\label{thm:maxconsbnp}
{\sc Max-$\B$-Consistency with Coincidence $1$ and Sparseness $2$} is
NP-complete.
\end{theorem}

\begin{proof}
  \cite{HoeffgenSimonvH:95} have shown that the maximum consistency
  problem for the class $\L$ and for samples without restrictions is
  NP-complete. They constructed a reduction from {\sc Vertex Cover}
  \cite[p.~190]{GareyJohnson:79}. This is the problem to decide, given
  a graph $G=(V,E)$ and a number $k$, whether there exists a set
  $V'\subseteq V$ with $|V'|\leq k$ such that for each edge
  $\{u,v\}\in E$ at least one of $u$ and $v$ belongs to $V'$. We use
  this problem for the reduction, too, but we take account of the fact
  that the weights are from the set $\{0,1\}$.
  
  Let $(V,E)$ and $k$ be an instance of {\sc Vertex Cover}, where
  $V=\{v_1,\dots,v_n\}$. We define the sample
  $S\subseteq\{0,1\}^{2n}\times \{0,1\}$ using the notation introduced
  in the proof of Theorem~\ref{thm:consbnp}. For each $v_i\in V$,
  there is a ``vertex example''
  \begin{eqnarray*}
    [i,n+i]_{2n} & \in & \Neg(S).
  \end{eqnarray*}
  Each $e=\{v_i,v_j\}\in E$ results in two ``edge examples''
  \begin{eqnarray*}
    [i,j]_{2n}     & \in & \Pos(S),\\[0mm]
    [n+i,n+j]_{2n} & \in & \Pos(S).
  \end{eqnarray*}
  The cardinality of the subsample in the instance of the maximum
  consistency problem is set to the value $|S|-k$.  It is obvious that
  $\Coin(S)\leq 1$ and $\Sparse(S)\leq 2$ holds, and that the reduction
  is computable in polynomial time.
  
  We claim that $(V,E)$ has a vertex cover of cardinality at most $k$
  if and only if there exists a function in $\B_{2n}$ that is
  consistent with at least $|S|-k$ examples. Let $V'\subseteq V$ be a
  vertex cover with at most $k$ elements. Define the weights
  $w_1,\dots,w_{2n}$ by
  \begin{equation*}
    \begin{array}{ccccc}
      w_i & = & w_{n+i} & = & \left\{
      \begin{array}{ll}
        1 & \text{if }v_i\in V',\\
        0 & \text{otherwise,}
      \end{array}\right.
    \end{array}
  \end{equation*}
  for $i=1,\dots,n$, and let the threshold be $t=1$. Then, the vertex
  example $[i,n+i]_{2n}$ is classified correctly if and only if
  $v_i\in V\setminus V'$. Further, since $V'$ is a vertex cover, all
  edge examples are classified correctly. Thus, the function computed
  by this neuron is consistent with at least $|S|-k$ elements.
  
  On the other hand, let the weights $w_1,\dots,w_{2n}$ and the
  threshold $t$ represent a function that is consistent with a
  subsample of $S$ of cardinality at least $|S|-k$.  Define a set $V'$
  of vertices as follows: For each vertex example that is classified
  wrongly include the corresponding vertex in $V'$; for each edge
  example that is classified wrongly arbitrarily choose one of the
  vertices the edge is incident with and include it in $V'$.
  Consequently, $V'$ contains at most $k$ elements. In order to show
  that $V'$ is a vertex cover, assume that $\{v_i,v_j\}\in E$ is not
  covered, that is, we have $\{v_i,v_j\}\cap V'=\emptyset$.  Then, by
  the construction of $V'$, the function is consistent with the two
  vertex examples that arose from $v_i$ and $v_j$, and it is
  consistent with the two edge examples due to $\{v_i,v_j\}$. Thus, we
  get
  \begin{eqnarray*}
    w_i + w_{n+i} + w_j + w_{n+j} & <    & 2t,\\
    w_i + w_j + w_{n+i} + w_{n+j} & \geq & 2t,
  \end{eqnarray*}
  a contradiction. This implies that $V^\prime$ is a vertex cover.
\end{proof}

The reduction defined in the previous proof remains valid under the
additional requirement that the threshold satisfies $t\leq 1$. As a
consequence, we obtain the NP-completeness result claimed by
Theorem~\ref{thm:maxconsbl}.

\begin{corollary}
\label{cor:maxconsblnp}
~For every $\ell\geq 1$, ~{\sc Max-$\B^\ell$-Consistency with Coincidence
  $1$ and Sparseness $2$} is NP-complete.
\end{corollary}

Furthermore, we observe that the proof of Theorem~\ref{thm:maxconsbnp}
does not make use of the assumption that the weights must be from the
set $\{0,1\}$.  Consequently, the reduction works also for
unconstrained weights, that is, for the function class $\L$. This
establishes the NP-completeness statement of
Theorem~\ref{thm:maxconsl}.

\begin{corollary}
  \label{cor:maxconslnp}
  {\sc Max-$\L$-Consistency with Coincidence $1$ and Sparseness $2$} is
  NP-complete.
\end{corollary}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Problems Solvable in Linear Time}
\label{sec:lineartimealgorithms}

In the following, we show that all consistency problems and maximum
consistency problems not yet considered in the foregoing section have
algorithms that run in linear time on a RAM as made precise in
Section~\ref{sec:lineartime}.  Thus, if P $\neq$ NP holds, the values
of coincidence and sparseness established in the NP-completeness
results are optimal.  Moreover, as any algorithm that solves a
consistency or maximum consistency problem must pass through the
entire sample, the linear-time bound cannot be improved either.  Thus,
we not only obtain a complete characterization of the complexity of
consistency problems for the function classes $\B$, $\B^\ell$, and
$\L$ with sample restrictions, but also reveal the striking fact that,
with respect to the RAM computer model, these classes consist solely
of problems of the lowest and highest complexity in NP. All algorithms
presented here are constructive, that is, they solve the decision
problem by computing a solution if one exists.


%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Consistency}
\label{subsec:lincons}

It is convenient to begin with the consistency problem for neurons
with a bounded threshold. The case that remains to be considered is
the function class $\B^1$. The result for this class implies the
second part of Theorem~\ref{thm:consbl}. It is valid for samples with
arbitrary coincidence and sparseness.

\begin{theorem}
\label{thm:consbonelin}
{\sc $\B^1$-Consistency} is solvable in linear time.
\end{theorem}

\begin{proof} If there are weights $w_1,\dots,w_n\in\{0,1\}$ and a
  threshold $t\in\{0,1\}$ consistent with a given sample $S$ then we
  may set $t=0$ if $\Neg(S)=\emptyset$. On the other hand, if $S$
  contains negative examples, we must have $t=1$. Then we ensure that
  $w\cdot x=0$ for all $x\in\Neg(S)$. These are the steps performed by
  Algorithm~\ref{alg:b1consistency}, which is basically the standard
  consistency algorithm for disjunctions.  The most time consuming
  part is the for-loop in lines 8--12. It is obvious that this
  statement can be implemented such that it requires no more than
  linear time on a RAM.
\end{proof}

\begin{algorithm}[ht]
\caption{\sc $\B^1$-Consistency}
\label{alg:b1consistency}
\begin{algorithmic}[1]
  \REQUIRE sample $S\subseteq\{0,1\}^n\times\{0,1\}$
  \ENSURE $w_1,\dots,w_n,t$
  \FOR{$i=1,\dots,n$}
    \STATE $w_i := 1$
  \ENDFOR;
  \IF{$\Neg(S) = \emptyset$}
    \STATE $t := 0$;
  \ELSE                      
    \STATE $t := 1$;
    \FORALL{$x\in\Neg(S)$}
      \IF{there is some $i\in\{1,\dots,n\}$ with $x_i=1$}
        \STATE $w_i := 0$
      \ENDIF
    \ENDFOR
  \ENDIF.
\end{algorithmic}
\end{algorithm}

It is easy to see that if some function in $\B$ is consistent with a
sample $S$ that has coincidence $0$, the threshold can be chosen to
satisfy $t\leq 1$. Therefore, Algorithm~\ref{alg:b1consistency} solves
also the problem {\sc $\B$-Consistency with Coincidence} $0$.

\begin{corollary}
\label{cor:consbcoinlin}
{\sc $\B$-Consistency with Coincidence} $0$ is solvable in linear
time.
\end{corollary}

Thus, the first of the two statements in Theorem~\ref{thm:consb} that
claim a linear time bound is covered. The second statement is
established by the following result.

\begin{theorem}
\label{thm:consbsparslin}
{\sc $\B$-Consistency with Sparseness $3$} is solvable in linear time.
\end{theorem}

\begin{proof} We show that Algorithm~\ref{alg:bconsistency} computes a
  solution for samples with sparseness $3$ provided that one exists.
  Without loss of generality we may assume that the threshold
  satisfies $t\leq 3$. The algorithm has three parts that correspond
  to the possible values for the threshold: $t\leq 1$, $t=3$, and
  $t=2$. In lines 1--2 Algorithm~\ref{alg:b1consistency} is used to
  check whether there is a function in the class $\B^1$ consistent
  with $S$.
  
  If this fails, the algorithm assumes in lines 3--12 that $t=3$.
  Here, the assignment of values to the weights is based on the fact
  that every positive example must reach the threshold. Hence, its
  non-zero components, of which there must be exactly three, specify
  which weights receive the value $1$.
  
  In the last part, starting from line~13, we can only have that
  $t=2$.  We show that this case of the consistency problem can be
  solved via a {\sc $2$-Satisfiability} problem. The algorithm maps
  the sample $S$ to a set $\C$ of clauses over the variables
  $w_1,\dots,w_n$.  Each clause has at most two literals of the form
  $w_i$ or $\neg w_i$. For each element $x\in\Dom(S)$ the set $\C$ is
  augmented with clauses that depend on the properties of $x$.  Lines
  17--23 deal with the case that $x$ has a $1$ in exactly three
  positions. If $x$ is a positive example then no two weights at these
  positions may both be equal to $0$. This is expressed by the three
  clauses in line 20.  If $x$ is a negative example then no two of
  these weights may both be equal to $1$.  This is taken into account
  by adding the three clauses in line 22.  Lines 24--30 treat the
  examples with exactly two $1$s. If $x$ is positive then both weights
  must be equal to $1$ (line~27); if $x$ is negative then at least one
  weight must be $0$ (line~29).  Finally, if $x$ has at most one
  non-zero position and $x$ is positive then the consistency problem
  has no solution.  This is taken care of in line~34 by adding two
  contradictory clauses. On the other hand, if $x$ is negative then it
  will be classified as such and nothing needs to be done. In the last
  step an algorithm for {\sc $2$-Satisfiability} is called with the
  constructed set of clauses as input.
  
  It remains to verify that the algorithm runs in linear time on a
  RAM.  Using Theorem~\ref{thm:consbonelin} we infer that the part in
  lines 1--14 requires no more than linear time. The construction of
  the set of clauses in lines 15--37 is performed in linear time.
  (Note that each example gives rise to at most three clauses.)
  Algorithms that compute satisfying assignments for {\sc
    $2$-Satisfiability} problems in linear time on a RAM with uniform
  measure have been designed by \cite{EvenItaiS:76} and
  \cite{AspvallPlassT:79}. It is obvious that the size of the
  constructed instance for {\sc $2$-Satisfiability} is at most linear
  in the size of the sample. Thus, line~38 can be executed in linear
  time.  We conclude that the running time of
  Algorithm~\ref{alg:bconsistency} on a random access machine is
  linear.
\end{proof}

\begin{algorithm}[ht]
\caption{\sc $\B$-Consistency}
\label{alg:bconsistency}
\begin{algorithmic}[1]
  \REQUIRE sample $S\subseteq\{0,1\}^n\times\{0,1\}$
  \ENSURE $w_1,\dots,w_n,t$
  \STATE get $w_1,\dots,w_n,t$ from $\B^1${\sc -Consistency($S$)};
  \STATE {\bf if} $(w_1,\dots,w_n,t)$ is consistent with $S$ {\bf
    then stop end if};
  \STATE $t := 3$;
  \FOR{$i = 1,\dots,n$}
      \STATE $w_i := 0$
  \ENDFOR;
  \FORALL{$x\in\Pos(S)$}
    \IF{there is some $x\in\Pos(S)$ with $x_i=1$}
      \STATE $w_i := 1$
    \ENDIF
  \ENDFOR;
  \STATE {\bf if} $(w_1,\dots,w_n,t)$ is consistent with $S$ {\bf
    then stop end if};
  \STATE $t := 2$;
  \STATE $\C := \emptyset$;
  \FORALL[construct a set $\C$ of clauses over
    $w_{1},\dots,w_{n}$]{$x\in\Dom(S)$}
    \STATE let $I = \{i \mid x_{i}=1\}$;
    \IF{$|I|=3$}
      \STATE let $\{j,k,\ell\} = I$;
      \IF{$x\in\Pos(S)$}
        \STATE $\C := \C \cup 
          \big\{\{w_j,w_k\},\{w_j,w_\ell\},\{w_k,w_\ell\}\big\}$
      \ELSE[we have $x\in\Neg(S)$]
        \STATE $\C := \C \cup \big\{\{\neg w_j,\neg w_k\},
          \{\neg w_j,\neg w_\ell\},\{\neg w_k,\neg w_\ell\}\big\}$
      \ENDIF
    \ELSIF{$|I|=2$}
      \STATE let $\{j,k\} = I$;
      \IF{$x\in\Pos(S)$}
        \STATE $\C := \C \cup \big\{\{w_j\},\{w_k\}\big\}$
      \ELSE[we have $x\in\Neg(S)$]
        \STATE $\C := \C \cup \big\{\{\neg w_j,\neg w_k\}\big\}$
      \ENDIF
    \ELSE[we have $|I|\leq 1$]
      \STATE {\bf if } $|I|=1$ {\bf then} let $\{j\} = I$ {\bf
        else} $j := 1$ {\bf end if};
      \IF{$x\in\Pos(S)$}
        \STATE $\C := \C \cup \big\{\{w_j\},\{\neg w_j\}\big\}$
      \ENDIF
    \ENDIF
  \ENDFOR ;
  \STATE get $w_1,\dots,w_n$ from {\sc
    $2$-Satisfiability($\{w_1,\dots,w_n\},\C$)}.
\end{algorithmic}
\end{algorithm}

With the previous result the proof of Theorem~\ref{thm:consb} is
completed. Obviously, Algorithm~\ref{alg:bconsistency} solves also the
consistency problems with sparseness $3$ for the classes $\B^\ell$
where $\ell\geq 2$. (If $\ell=2$, the middle part of the algorithm,
which assumes $t=3$, is needless.)  Furthermore, if some function in
$\B^\ell$ is consistent with a sample having coincidence $0$ then
there is also some function in $\B^1$ consistent with that sample.
Consequently, Algorithm~\ref{alg:b1consistency} solves also the
problems {\sc $\B^\ell$-Consistency with Coincidence $0$} for every
$\ell\geq 2$.  Hence, Theorems and~\ref{thm:consbsparslin}
and~\ref{thm:consbonelin} yield the following statement. It finalizes
the proof of Theorem~\ref{thm:consbl}.

\begin{corollary}
\label{cor:consbonesparslin}
For every $\ell\geq 2$, {\sc $\B^\ell$-Consistency with Coincidence
  $0$} and {\sc $\B^\ell$-Consist\-ency with Sparseness $3$} is solvable
in linear time.
\end{corollary}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Maximum Consistency}
\label{subsec:linmaximum}

At last, we give attention to the maximum consistency problems that
are claimed as linear-time solvable in Theorems~\ref{thm:maxconsb},
\ref{thm:maxconsbl}, and~\ref{thm:maxconsl}. The main issues that have
to be dealt with are contradictory pairs and examples that are $0$ in
all positions.  With the first result we finish the proof of
Theorem~\ref{thm:maxconsb}.

\begin{theorem}
\label{thm:maxconsblin}
The problems {\sc Max-$\B$-Consistency with Coincidence $0$} and {\sc
  Max-$\B$-Consistency with Sparseness $1$} are solvable in linear time.
\end{theorem}

\begin{proof} If $\Neg(S)=\emptyset$ then by letting $w_1 = \dots = w_n =
  0$ and $t=0$ we obtain the function that always outputs $1$, which
  is consistent with all examples. Assume now that
  $\Neg(S)\neq\emptyset$. Algorithm~\ref{alg:maxbconsistency}
  generates a function that has the following properties: For each
  example $x\in\Dom(S)$ that is part of a contradictory pair, that is,
  where $(x,0)\in S$ and $(x,1)\in S$, the function is consistent with
  the positive example. Further, it is consistent with all examples
  that are not part of a contradictory pair, except possibly for the
  example $(0,\dots,0)\in \Pos(S)\setminus\Neg(S)$, which is
  classified as negative. It is obvious that this is the maximum
  number of examples that can be classified correctly, unless
  $(0,\dots,0)\in \Pos(S)\setminus\Neg(S)$ is the only example that is
  not part of a contradictory pair. In this case we can increase the
  number of correctly classified examples by using the function that
  constantly outputs $1$, which is then consistent with the positive
  example in each contradictory pair and with $(0,\dots,0)\in\Pos(S)$.
  
  It is obvious that Algorithm~\ref{alg:maxbconsistency} and the
  additional steps described above require no more than linear time on
  a RAM.  In particular, whether $(0,\dots,0)$ is the only example
  that is not part of a contradictory pair can be checked in linear
  time using radix sort.

  If $\Sparse(S)=1$ then we proceed in the same way. In order to see
  that this is correct, observe that $\Coin(S)=1$ holds only if $S$
  contains examples $(x,0)$ and $(x,1)$. Thus, a maximum subsample
  $S'$ that does not contain contradictory pairs satisfies
  $\Coin(S')=0$.
\end{proof}

\begin{algorithm}[ht]
\caption{\sc Max-$\B$-Consistency}
\label{alg:maxbconsistency}
\begin{algorithmic}
  \REQUIRE sample $S\subseteq\{0,1\}^n\times\{0,1\}$ 
  \ENSURE $w_1,\dots,w_n,t$ 
  \STATE $t := 1$; 
  \FOR{$i=1,\dots,n$} 
    \STATE $w_i := 0$ 
  \ENDFOR; 
  \FORALL{$x\in\Pos(S)$} 
    \IF{there is some $i\in\{1,\dots,n\}$ with $x_i=1$} 
      \STATE $w_i := 1$ 
    \ENDIF
  \ENDFOR.
\end{algorithmic}
\end{algorithm}

The algorithm presented in the foregoing proof generates only
solutions where the threshold is at most $1$. Thus, it solves also the
corresponding problems for neurons with a bounded threshold as was
claimed in the first statement of Theorem~\ref{thm:maxconsbl}.

\begin{corollary}
\label{cor:maxconsbllin}
For every $\ell\geq 1$, {\sc Max-$\B^\ell$-Consistency with
  Coincidence $0$} and {\sc Max-$\B^\ell$-Consistency with Sparseness
  $1$} is solvable in linear time.
\end{corollary}

The following result completes the proof of
Theorem~\ref{thm:maxconsbl}.

\begin{lemma}
  \label{lem:maxconsb0lin}
  {\sc Max-$\B^0$-Consistency} is solvable in linear time.
\end{lemma}

\begin{proof}
  If the threshold is equal to $0$ then everything is classified as
  positive regardless of which values the weights may have. Thus,
  outputting any weights and $t=0$ provides a solution if one exists.
  For solving the decision problem, observe that consistency with at
  least $k$ examples in $S$ is equivalent to the condition
  $|\Pos(S)|\geq k$. This can clearly be checked in linear time on a
  RAM.
\end{proof}

Finally, we prove the remaining part of Theorem~\ref{thm:maxconsl}
that claims linear time bounds.

\begin{theorem}
  \label{thm:maxconsllin}
  The problems {\sc Max-$\L$-Consistency with Coincidence $0$} and
  {\sc Max-$\L$-Consistency with Sparseness $1$} are solvable in linear
  time.
\end{theorem}

\begin{proof}
  Consider Algorithm~\ref{alg:maxlconsistency} for inputs satisfying
  $\Coin(S)=0$. If $\Neg(S)=\emptyset$ then the resulting function is
  consistent with all examples. In the case that
  $\Neg(S)\neq\emptyset$ holds we argue as in the proof of
  Theorem~\ref{thm:maxconsblin}: For every contradictory pair, the
  function is consistent with the positive example. Further, it is
  consistent with every example that is not part of a contradictory
  pair.  (In contrast to the proof of Theorem~\ref{thm:maxconsblin},
  this holds also in all cases where $(0,\dots,0)\in\Dom(S)$ due to
  the use of negative weights by Algorithm~\ref{alg:maxlconsistency}.)
  Clearly, this is the maximum number of examples a function can be
  consistent with.
  
  Since any subsample $S'$ of $S$ that contains no contradictory pairs
  must satisfy $\Coin(S')=0$ if $\Sparse(S)=1$,
  Algorithm~\ref{alg:maxlconsistency} solves also the maximum
  consistency problem for samples with sparseness $1$.
  
  That the running time of Algorithm~\ref{alg:maxlconsistency} is
  linear on a RAM is obvious.
\end{proof} 
  
\begin{algorithm}[ht]
\caption{\sc Max-$\L$-Consistency}
\label{alg:maxlconsistency}
\begin{algorithmic}
  \REQUIRE sample $S\subseteq\{0,1\}^n\times\{0,1\}$
  \ENSURE $w_1,\dots,w_n,t$
  \IF{$(0,\dots,0)\in\Pos(S)$}
    \STATE $t := 0$
  \ELSE
    \STATE $t := 1$
  \ENDIF;
  \FOR{$i = 1,\dots,n$}
      \STATE $w_i := -1$
  \ENDFOR;
  \FORALL{$x\in\Pos(S)$}
    \IF{there is some $i\in\{1,\dots,n\}$ with $x_i=1$}
      \STATE $w_i := 1$
    \ENDIF
  \ENDFOR.
\end{algorithmic}
\end{algorithm}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Conclusions}
\label{sec:conclusions}

With this work we aimed at providing necessary and sufficient
conditions for the existence of efficient learning algorithms. The
approach that we have taken is to consider criteria for the complexity
of samples and to use them for the definition of subproblems. As
results we obtained dichotomy theorems that completely characterize
the dividing lines between the polynomial-time solvable and the
NP-complete problems.

An NP-completeness assertion is a worst-case result stating that, if P
$\neq$ NP then there is no algorithm that solves the problem in
polynomial time for all instances. One way to cope with intractability
is therefore trying to avoid instances that make the problem hard.
This gives rise to subproblems that may be more appropriate to
practical situations where one often needs not deal with all possible
instances but only a subset thereof. The results here show that such
deliberations can indeed lead to the discovery of new efficient
learning algorithms.  While it is not clear whether the restrictions
they suppose are always met in applications, these algorithms could be
helpful in the development of better heuristics for more general
learning problems.

A number of questions arises from this work that are worth further
investigation. We have considered only two types of neural
``networks'': single neurons with binary and with arbitrary weights.
Whether dichotomy theorems can be established for other neuron types
and for neural networks is an interesting open problem. Further, the
problems we have studied can be generalized by allowing examples with
integer or even rational components. While the NP-completeness results
remain valid in these cases, it is not obvious how the algorithms can
be adapted to deal with non-binary inputs. Finally, we have introduced
here two specific criteria for sample restrictions.  Motivated by
theoretical or practical considerations one can think of many other
ways to select such conditions.
\newpage
\acks{I thank the anonymous reviewers for their helpful comments and
  suggestions. This work was supported in part by the IST Programme of
  the European Community, under the PASCAL Network of Excellence,
  IST-2002-506778.}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\appendix
\section{An NP-Complete Satisfiability Problem}

Lemma~\ref{lem:1in3sat} in Section~\ref{subsec:npconsistency} claims
that the problem {\sc Almost Disjoint Positive 1-in-3Sat} introduced
in that section is NP-complete. Here we give a proof of this
statement.

\setcounter{theorem}{5}
\begin{lemma}
{\sc Almost Disjoint Positive 1-in-3Sat} is NP-complete.
\end{lemma}

\begin{proof}
  It is clear that the problem is in NP. To prove its NP-hardness, we
  construct a reduction from {\sc Positive 1-in-3Sat}. In this variant
  of the problem the requirement is missing that two subsets have at
  most one variable in common. The idea of the reduction is to
  establish the property of almost disjointness by introducing new
  variables as substitutes for old ones. The correctness of the
  reduction is ensured by augmenting the collection with additional
  subsets.
  
  Let $\C$ be the collection of subsets from the instance of {\sc
    Positive 1-in-3Sat}. Further, let $C,D\in\C$ be two subsets with
  two common variables, say $C=\{u_1,u_2,u_3\}$ and
  $D=\{u_1,u_2,u_4\}$. We introduce a set of new variables
  $V=\{v_1,\dots,v_5\}$, replace in $D$ the variable $u_1$ by $v_1$
  and join $\C$ with the collection $\D$ defined as
  \begin{eqnarray*}
    \D & = & \big\{\{v_1,v_2,v_3\}, ~\{v_1,v_4,v_5\}, ~\{u_1,v_2,v_4\},
    ~\{u_1,v_3,v_5\}\big\}.
  \end{eqnarray*}
  Obviously, no pair of subsets in $\D$ has more than one common
  variable. Further, no subset in $\D$ has more than one variable in
  common with any subset in $\C$. Hence, going from $\C$ to
  $\C\cup\D$, the number of pairs that violate the condition of almost
  disjointness decreases by one.
  
  We say that a truth assignment is a {\sc 1-in-3Sat} assignment for a
  collection of subsets if each subset has exactly one true variable.
  Let $U$ be the set of variables in $\C$. We claim that the following
  two conditions hold:
  \begin{quote}
  \begin{itemize}
  \item[(A.1)] Every {\sc 1-in-3Sat} assignment $\alpha:U\to\{0,1\}$
    for $\C$ can be extended to a {\sc 1-in-3Sat} assignment
    $\alpha:U\cup V\to\{0,1\}$ for $\C\cup\D$ satisfying
    $\alpha(u_1)=\alpha(v_1)$.
  \item[(A.2)] Every {\sc 1-in-3Sat} assignment $\alpha:U\cup
    V\to\{0,1\}$ for $\C\cup\D$ satisfies $\alpha(u_1)=\alpha(v_1)$.
  \end{itemize}
  \end{quote}
  That condition~(A.1) is valid can be seen as follows: Given $\alpha$
  defined on $U$, we let $\alpha(v_1)=\alpha(u_1)$ and extend it to
  the remaining variables of $V$ in the following way: In the case
  $\alpha(u_1)=0$ we define $\alpha(v_2)=\alpha(v_5)=0$ and
  $\alpha(v_3)=\alpha(v_4)=1$; in the case $\alpha(u_1)=1$ we let
  $\alpha(v_2)=\alpha(v_3)=\alpha(v_4)=\alpha(v_5)=0$. For the proof
  of condition~(A.2) we observe that if $\alpha(v_1)=1$, we must have
  $\alpha(v_2)=\alpha(v_3)=\alpha(v_4)=\alpha(v_5)=0$ due to the first
  two subsets in $\D$, and hence, because of the last two subsets,
  $\alpha(u_1)=1$; on the other hand, if $\alpha(u_1)=1$, analogous
  reasoning yields that $\alpha(v_1)=1$ must hold. Thus, $u_1$ and
  $v_1$ cannot have different truth values assigned by $\alpha$.
  
  Conditions~(A.1) and~(A.2) imply that $\C$ has a {\sc 1-in-3Sat}
  assignment if and only if $\C\cup\D$ has a {\sc 1-in-3Sat}
  assignment. Repeating the above described procedure for every pair
  of subsets with two common variables we finally arrive at a
  collection that is almost disjoint. The correctness of the reduction
  follows inductively. It is obvious that the reduction is computable
  in polynomial time. Thus, {\sc Almost Disjoint Positive 1-in-3Sat}
  is NP-hard.
\end{proof}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{thebibliography}{}

\bibitem[Amaldi, 1991]{Amaldi:91}
Amaldi, E. (1991).
\newblock On the complexity of training {P}erceptrons.
\newblock In Kohonen, T., M\"{a}kisara, K., Simula, O., and Kangas, J.,
  editors, {\em Artificial Neural Networks}, pages 55--60. Elsevier, Amsterdam.

\bibitem[Anthony and Bartlett, 1999]{AnthonyBartlett:99}
Anthony, M. and Bartlett, P.~L. (1999).
\newblock {\em Neural Network Learning: Theoretical Foundations}.
\newblock Cambridge University Press, Cambridge.

\bibitem[Aspvall et~al., 1979]{AspvallPlassT:79}
Aspvall, B., Plass, M.~F., and Tarjan, R.~E. (1979).
\newblock A linear-time algorithm for testing the truth of certain quantified
  {B}oolean formulas.
\newblock {\em Information Processing Letters}, 8:121--123.

\bibitem[Blum and Rivest, 1992]{BlumRivest:92}
Blum, A.~L. and Rivest, R.~L. (1992).
\newblock Training a 3-node neural network is {NP}-complete.
\newblock {\em Neural Networks}, 5:117--127.

\bibitem[Blumer et~al., 1989]{BlumerEhrenfeuchtHW:89}
Blumer, A., Ehrenfeucht, A., Haussler, D., and Warmuth, M.~K. (1989).
\newblock Learnability and the {V}apnik-{C}hervonenkis dimension.
\newblock {\em Journal of the Association for Computing Machinery},
  36:929--965.

\bibitem[Cook and Reckhow, 1973]{CookReckhow:73}
Cook, S.~A. and Reckhow, R.~A. (1973).
\newblock Time bounded random access machines.
\newblock {\em Journal of Computer and System Sciences}, 7:354--375.

\bibitem[Dalmau, 1999]{Dalmau:99}
Dalmau, V. (1999).
\newblock A dichotomy theorem for learning quantified {B}oolean formulas.
\newblock {\em Machine Learning}, 35:207--224.

\bibitem[Dalmau and Jeavons, 2003]{DalmauJeavons:03}
Dalmau, V. and Jeavons, P. (2003).
\newblock Learnability of quantified formulas.
\newblock {\em Theoretical Computer Science}, 306:485--511.

\bibitem[Even et~al., 1976]{EvenItaiS:76}
Even, S., Itai, A., and Shamir, A. (1976).
\newblock On the complexity of timetable and multicommodity flow problems.
\newblock {\em SIAM Journal on Computing}, 5:691--703.

\bibitem[Fang and Venkatesh, 1996]{FangVenkatesh:96}
Fang, S.~C. and Venkatesh, S.~S. (1996).
\newblock Learning binary {P}erceptrons perfectly efficiently.
\newblock {\em Journal of Computer and System Sciences}, 52:374--389.

\bibitem[Garey and Johnson, 1979]{GareyJohnson:79}
Garey, M.~R. and Johnson, D.~S. (1979).
\newblock {\em Computers and Intractability: A Guide to the Theory of
  NP-Completeness}.
\newblock W. H. Freeman, San Francisco.

\bibitem[Golea and Marchand, 1993]{GoleaMarchand:93}
Golea, M. and Marchand, M. (1993).
\newblock On learning {P}erceptrons with binary weights.
\newblock {\em Neural Computation}, 5:767--782.

\bibitem[Hampson and Volper, 1986]{HampsonVolper:86}
Hampson, S.~E. and Volper, D.~J. (1986).
\newblock Linear function neurons: Structure and training.
\newblock {\em Biological Cybernetics}, 53:203--217.

\bibitem[Haykin, 1999]{Haykin:99}
Haykin, S. (1999).
\newblock {\em Neural Networks: A Comprehensive Foundation}.
\newblock Prentice Hall, Upper Saddle River, NJ, second edition.

\bibitem[H\"{o}ffgen et~al., 1995]{HoeffgenSimonvH:95}
H\"{o}ffgen, K.-U., Simon, H.-U., and {Van Horn}, K.~S. (1995).
\newblock Robust trainability of single neurons.
\newblock {\em Journal of Computer and System Sciences}, 50:114--125.

\bibitem[Judd, 1990]{Judd:90}
Judd, J.~S. (1990).
\newblock {\em Neural Network Design and the Complexity of Learning}.
\newblock The MIT Press, Cambridge, MA.

\bibitem[Kearns et~al., 1994]{KearnsSchapireS:94}
Kearns, M.~J., Schapire, R.~E., and Sellie, L.~M. (1994).
\newblock Toward efficient agnostic learning.
\newblock {\em Machine Learning}, 17:117--141.

\bibitem[Kim and Roche, 1998]{KimRoche:98}
Kim, J.~H. and Roche, J.~R. (1998).
\newblock Covering cubes by random half cubes, with applications to binary
  neural networks.
\newblock {\em Journal of Computer and System Sciences}, 56:223--252.

\bibitem[Kirousis and Kolaitis, 2003]{KirousisKolaitis:03}
Kirousis, L.~M. and Kolaitis, P.~G. (2003).
\newblock The complexity of minimal satisfiability problems.
\newblock {\em Information and Computation}, 187:20--39.

\bibitem[Littlestone, 1988]{Littlestone:88}
Littlestone, N. (1988).
\newblock Learning quickly when irrelevant attributes abound: A new
  linear-threshold algorithm.
\newblock {\em Machine Learning}, 2:285--318.

\bibitem[Maass and Tur{\'a}n, 1994]{MaassTuran:94}
Maass, W. and Tur{\'a}n, G. (1994).
\newblock How fast can a threshold gate learn?
\newblock In Hanson, S.~J., Drastal, G., and Rivest, R., editors, {\em
  Computational Learning Theory and Natural Learning Systems: Constraints and
  Prospects}, pages 381--414. The MIT Press, Cambridge, MA.

\bibitem[McCulloch and Pitts, 1943]{McCullochPitts:43}
McCulloch, W.~S. and Pitts, W. (1943).
\newblock A logical calculus of the ideas immanent in nervous activity.
\newblock {\em Bulletin of Mathematical Biophysics}, 5:115--133.

\bibitem[Natarajan, 1991]{Natarajan:91}
Natarajan, B.~K. (1991).
\newblock {\em Machine Learning: A Theoretical Approach}.
\newblock Morgan Kaufmann, San Mateo, CA.

\bibitem[Palm, 1980]{Palm:80}
Palm, G. (1980).
\newblock On associative memory.
\newblock {\em Biological Cybernetics}, 36:19--31.

\bibitem[Pitt and Valiant, 1988]{PittValiant:88}
Pitt, L. and Valiant, L.~G. (1988).
\newblock Computational limitations on learning from examples.
\newblock {\em Journal of the Association for Computing Machinery},
  35:965--984.

\bibitem[Schaefer, 1978]{Schaefer:78}
Schaefer, T.~J. (1978).
\newblock The complexity of satisfiability problems.
\newblock In {\em Proceedings of the 10th Annual ACM Symposium on Theory of
  Computing}, pages 216--226.

\bibitem[Schmitt, 1994a]{94a:Schmitt}
Schmitt, M. (1994a).
\newblock On the complexity of consistency problems for neurons with binary
  weights.
\newblock Ulmer Informatik-Berichte 94-01, Universit{\"a}t Ulm.

\bibitem[Schmitt, 1994b]{94b:Schmitt}
Schmitt, M. (1994b).
\newblock On the size of weights for {M}c{C}ulloch-{P}itts neurons.
\newblock In Caianiello, E.~R., editor, {\em Proceedings of the Sixth Italian
  Workshop on Neural Nets WIRN VIETRI-93}, pages 241--246, World Scientific,
  Singapore.

\bibitem[Schmitt, 1995]{95c:Schmitt}
Schmitt, M. (1995).
\newblock On methods to keep learning away from intractability.
\newblock In Fogelman-Souli\'e, F. and Gallinari, P., editors, {\em Proceedings
  of the International Conference on Artificial Neural Networks ICANN '95},
  volume~1, pages 211--216, EC2 \& Cie., Paris.

\bibitem[Servedio, 2002]{Servedio:02}
Servedio, R.~A. (2002).
\newblock Perceptron, {W}innow, and {PAC} learning.
\newblock {\em SIAM Journal on Computing}, 31:1358--1369.

\bibitem[Sommer and Palm, 1999]{SommerPalm:99}
Sommer, F.~T. and Palm, G. (1999).
\newblock Improved bidirectional retrieval of sparse patterns stored by
  {H}ebbian learning.
\newblock {\em Neural Networks}, 12:281--297.

\bibitem[{van Emde Boas}, 1990]{vanEmdeBoas:90}
{van Emde Boas}, P. (1990).
\newblock Machine models and simulations.
\newblock In {van Leeuwen}, J., editor, {\em Handbook of Theoretical Computer
  Science}, volume A: Algorithms and Complexity, chapter~1, pages 1--66.
  Elsevier, Amsterdam.

\bibitem[\v{S}\'{\i}ma, 2002]{Sima:02}
\v{S}\'{\i}ma, J. (2002).
\newblock Training a single sigmoidal neuron is hard.
\newblock {\em Neural Computation}, 14:2709--2728.

\bibitem[Zheng and Stuckey, 2002]{ZhengStuckey:02}
Zheng, L. and Stuckey, P.~J. (2002).
\newblock Improving {SAT} using {2SAT}.
\newblock In Oudshoorn, M.~J., editor, {\em Proceedings of the Twenty-Fifth
  Australasian Computer Science Conference ACSC2002}, volume~4 of {\em
  Conferences in Research and Practice in Information Technology}, pages
  331--340, Australian Computer Society, Sydney.

\end{thebibliography}

\end{document}
