ANALOG COMPUTATION VIA NEURAL NETWORKS

被引:217
作者
SIEGELMANN, HT [1 ]
SONTAG, ED [1 ]
机构
[1] RUTGERS STATE UNIV,DEPT MATH,NEW BRUNSWICK,NJ 08903
关键词
D O I
10.1016/0304-3975(94)90178-3
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
We pursue a particular approach to analog computation, based on dynamical systems of the type used in neural networks research. Our systems have a fixed structure, invariant in time, corresponding to an unchanging number of neurons''. If allowed exponential time for computation, they turn out to have unbounded power. However, under polynomial-time constraints there are limits on their capabilities, though being more powerful than Turing machines. (A similar but more restricted model was shown to be polynomial-time equivalent to classical digital computation in the previous work (Siegelmann and Sontag, 1992).) Moreover, there is a precise correspondence between nets and standard nonuniform circuits with equivalent resources, and as a consequence one has lower bound constraints on what they can compute. This relationship is perhaps surprising since our analog devices do not change in any manner with input size. We note that these networks are not likely to solve polynomially NP-hard problems, as the equality ''P=NP'' in our model implies the almost complete collapse of the standard polynomial hierarchy. In contrast to classical computational models, the models studied here exhibit at least some robustness with respect to noise and implementation errors.
引用
收藏
页码:331 / 360
页数:30
相关论文
共 23 条
[1]  
Alspector J., 1987, Advanced Research in VLSI. Proceedings of the 1987 Stanford Conference, P313
[2]  
Atkinson KE, 1989, INTRO NUMERICAL ANAL, Vsecond
[3]  
BALCAZAR JL, 1988, STRUCTURAL COMPLEXIT
[4]   ON A THEORY OF COMPUTATION AND COMPLEXITY OVER THE REAL NUMBERS - NP-COMPLETENESS, RECURSIVE FUNCTIONS AND UNIVERSAL MACHINES [J].
BLUM, L ;
SHUB, M ;
SMALE, S .
BULLETIN OF THE AMERICAN MATHEMATICAL SOCIETY, 1989, 21 (01) :1-46
[5]   CONSTANT DEPTH REDUCIBILITY [J].
CHANDRA, AK ;
STOCKMEYER, L ;
VISHKIN, U .
SIAM JOURNAL ON COMPUTING, 1984, 13 (02) :423-439
[6]  
Eberhardt S. P., 1989, NEURAL NETWORKS, V4, P431
[7]  
Furst M., 1981, 22nd Annual Symposium on Foundations of Computer Science, P260, DOI 10.1109/SFCS.1981.35
[8]   LEARNING AND EXTRACTING FINITE STATE AUTOMATA WITH 2ND-ORDER RECURRENT NEURAL NETWORKS [J].
GILES, CL ;
MILLER, CB ;
CHEN, D ;
CHEN, HH ;
SUN, GZ ;
LEE, YC .
NEURAL COMPUTATION, 1992, 4 (03) :393-405
[9]   ON CONNECTIONIST MODELS [J].
HONG, JW .
COMMUNICATIONS ON PURE AND APPLIED MATHEMATICS, 1988, 41 (08) :1039-1050
[10]  
Karp R.M., 1982, ENSEIGN MATH, V28, P191