Finding approximate solutions to NP-hard problems by neural networks is hard

Research output: Journal PublicationsJournal Article (refereed)peer-review

15 Citations (Scopus)


Finding approximate solutions to hard combinatorial optimization problems by neural networks is a very attractive prospect. Many empirical studies have been done in the area. However, recent research about a neural network model indicates that for any NP-hard problem the existence of a polynomial size network that solves it implies that NP=co-NP, which is contrary to the well-known conjecture that NP ≠ co-NP. This paper shows that even finding approximate solutions with guaranteed performance to some NP-hard problems by a polynomial size network is also impossible unless NP = co-NP. © 1992.
Original languageEnglish
Pages (from-to)93-98
Number of pages6
JournalInformation Processing Letters
Issue number2
Publication statusPublished - Feb 1992
Externally publishedYes


  • Neural networks, combinatorial optimization, computational complexity


Dive into the research topics of 'Finding approximate solutions to NP-hard problems by neural networks is hard'. Together they form a unique fingerprint.

Cite this