PUMA
Istituto di Scienza e Tecnologie dell'Informazione     
Codenotti B., Margara L. Local properties of some np-complete problems. Internal note IEI-B4-20, 1991.
 
 
Abstract
(English)
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.
Subject


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