lipscomb@ai.toronto.edu (John Lipscomb) (04/08/88)
Two M.Sc. theses are available by writing or e-mailing me.
They are
The Computational Complexity of
the Stable Configuration Problem
for Connectionist Models
Gail H. Godbeer
September 1987
(latex typesetting)
\begin {abstract}
Connectionist models (CM's) are typically used to perform
constraint-satisfaction searches.
We know that the problem of finding the configuration
that least violates the constraints in a CM is $NP$-hard.
We thus look at the complexity of finding {\em stable} configurations,
or configurations in which all the local constraints are satisfied.
The complexity of finding a stable configuration varies greatly
depending on the type of weights in a CM. We thus classify CM's
according to their weights and examine the parallel and sequential complexity
of this problem for the various classes.
\end {abstract}
AND
On the Computational Complexity of Finding
a Connectionist Model's Stable State Vectors
John Lipscomb
October 1987
\newcommand{\cm}{{\sc cm}}
\newcommand{\ssv}{stable state vector}
\begin{abstract}
Our {\em Connectionist Models\/} (\cm's) are fixed weighted simple graphs
where each node can be in one of two states: {\em on}\/ or {\em off}.
A {\em \ssv\/} for a \cm\ is an assignment of states to the
nodes such that each node is stable.
The stability of a node depends on its state, its weight,
incident edge weights, and neighboring nodes' states.
Our principle results are
\begin{itemize}
\item The decision problem ``Given a directed \cm, does it have a \ssv?''
is NP-complete.
\item The search problem ``Given an undirected \cm, find a \ssv\ for it.''
is P-hard under \NC{1} reductions.
\item The decision problem ``Given an undirected \cm, does it have at
least two different \ssv s?'' is NP-complete.
\item The decision problem ``Given an undirected \cm,
a node $x$, and a state $s$, does the \cm\
have a \ssv\ with node $x$ in state $s$?'' is NP-complete.
\end{itemize}
We consider the complexity of these problems
on more restricted classes of \cm's, and prove that
the problem of finding a \ssv\ can be solved in O($m$) sequential time,
where $m$ is the number of edges, for \cm's with only
positive edges or for bipartite \cm's with only negative edges.
The obvious major question is still open:
``Is there a poly-time algorithm for finding
a \ssv\ for an undirected \cm?''
Also of interest is whether any interesting restricted
class of \cm's has a fast parallel algorithm for finding a \ssv.
\end{abstract}
The theses overlap in parts, but the
different perspective is worthwhile.
John Lipscomb
Dept. of Computer Sc.
University of Toronto
Toronto, Canada
M5S 1A4
(416) 978-4837
home ph: 928-3310
electronic mail:
lipscomb@ai.toronto.edu (CSnet,UUCP,Bitnet)
{uunet,watmath}!ai.toronto.edu!lipscomb