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

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.
hopfield networks, min energy, polynomial time approximation
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.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11562/16329
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact