ATTRACTION RADII IN BINARY HOPFIELD NETS ARE HARD TO COMPUTE

被引：18

作者：

FLOREEN, P

ORPONEN, P

机构：

来源：

NEURAL COMPUTATION | 1993年 / 5卷 / 05期

关键词：

D O I：

10.1162/neco.1993.5.5.812

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

We prove that it is an NP-hard problem to determine the attraction radius of a stable vector in a binary Hopfield memory network, and even that the attraction radius is hard to approximate. Under synchronous updating, the problems are already NP-hard for two-step attraction radii; direct (one-step) attraction radii can be computed in polynomial time.

引用

页码：812 / 821

页数：10

共 11 条

[1]

Floreen P., 1989, COMPLEX SYST, V3, P577

[2]

Garey M. R., 1979, COMPUTERS INTRACTABI

[3]

GODBEER GH, 1988, 20888 U TOR DEP COMP

[4] DECREASING ENERGY FUNCTIONS AS A TOOL FOR STUDYING THRESHOLD NETWORKS [J].

GOLESCHACC, E ;

FOGELMANSOULIE, F ;

PELLEGRIN, D .

DISCRETE APPLIED MATHEMATICS, 1985, 12 (03) :261-277

[5]

HALLDORSSON MM, 1993, JAIST ISRR930001F JA

[6] NEURAL NETWORKS AND PHYSICAL SYSTEMS WITH EMERGENT COLLECTIVE COMPUTATIONAL ABILITIES [J].

HOPFIELD, JJ .

PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA-BIOLOGICAL SCIENCES, 1982, 79 (08) :2554-2558

[7]

KANN V, 1992, COMMUNICATION

[8]

ORPONEN P, 1992, LECT NOTES COMPUT SC, V629, P50

[9]

PANCONESI A, 1990, 22ND P ANN ACM S THE, P446

[10]

PARBERRY I, 1990, FORMAL TECHNIQUES AR, P217

← 1 2 →