Istituto di Scienza e Tecnologie dell'Informazione     
Codenotti B., Margara L. Local properties of some np-complete problems. Internal note IEI-B4-20, 1991.
In (GR089A) it is shown that some NP-complete problems with certain notions of "neighbour" satisfy a difference equation that is similar to the wave equation of mathematical physics. In this paper we extend some results presented In (GR089A). More precisely we show that other problems do exist that satisfy the difference equation presented by Grover and we analyse some properties of the local structure of the NP-complete problems which satisfy the difference equation.

Icona documento 1) Download Document PDF

Icona documento Open access Icona documento Restricted Icona documento Private


Per ulteriori informazioni, contattare: Librarian http://puma.isti.cnr.it

Valid HTML 4.0 Transitional