kslee@demon.siemens-rtl (Kangsuk Lee) (03/12/88)
.EQ
delim $$
.EN
.nr PS 11
.ps 11
.EQ
gsize 11
.EN
.LP
.ce
\fBSome Perspectives on Analog Computation\fR
.sp
.ce 4
\fIBradley W. Dickinson\fR
Dept. of Electrical Engineering
Princeton University
Princeton, NJ 08544
.sp
.ce
\fBDate: March 23 (Wed) 10:00 \fR
.sp
.ce
\fBPlace: Siemens RTL, Princeton NJ \fR
.sp
.ce
\fBContact: Tom Petsche (609) 734-3392\fR
.sp
.PP
The term \fIanalog computation\fR evokes numerous associations; the
planimeter, the slide rule, the differential analyzer, and other
physical computing systems are modeled by mathematical equations
with diverse applications. By drawing a careful distinction between
analog and digital computation, it becomes possible to compare the
use of analog computation in the solution of various optimization
problems with the use of digital computation.
Can analog computation be used to solve intractable combinatorial
optimization problems, circumventing the apparent limitations of
digital computation? We will argue that this is unlikely, based on a
simulation paradigm.
.PP
Differential equation models associated with $bold { NP }$-complete
problems have been proposed in the literature. These provide an
opportunity to explore and develop interesting complexity issues
related to dynamic systems. A common shortcoming is the failure of the
model to admit a scaling that constrains the solutions to evolve in a
polynomially-bounded hypercube in ``configuration-space'', for a fixed
level of precision of the computation. Analog sorting schemes
provide a simple illustration of this inherent
obstacle to solution of ``numerical'' problems by analog means.
The differential equation models for ``nonnumerical'' problems
can also suffer from this drawback. One topic to be discussed
is the ``neural network'' formulation proposed by
Hopfield and Tank for the solution of the $bold { NP }$-complete
Traveling Salesman Problem with systems described
by differential equations. The scaling problem in this model arises from
the use of highly nonlinear amplifier characteristics.
.PP
Time permitting, some possible connections with ergodic theory and
complex dynamics (chaos) will be mentioned. It appears that even
in dynamic systems where scaling problems do not arise, the ability to
do computation may be severely limited.
Kangsuk Lee, Siemens RTL Learning Systems Lab
105 College Road, Princeton, NJ 08540
e-mail: kslee@siemens.com or princeton!siemens!kslee