We consider polynomial-time algorithms for finding approximate solutions of the ground state problem for Hopfield network where the neurons are arranged on a two-level grid. We prove: 1. there is an approximate polynomial-time algorithm with absolute error O( n lg n ); 2. there exists a constant fi ? 0 such that for fl ! 1 every approximate polynomial-time algorithm has absolute error greater than fin fl infinitely often, unless P=NP.
Polynomial Time Approximation of Min-Energy in Hopfield Networks
POSENATO, Roberto
1995-01-01
Abstract
We consider polynomial-time algorithms for finding approximate solutions of the ground state problem for Hopfield network where the neurons are arranged on a two-level grid. We prove: 1. there is an approximate polynomial-time algorithm with absolute error O( n lg n ); 2. there exists a constant fi ? 0 such that for fl ! 1 every approximate polynomial-time algorithm has absolute error greater than fin fl infinitely often, unless P=NP.
File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
