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 |

1) Download Document PDF |

Open access Restricted Private