Résolutions universelles pour des problèmes NP-complets.



Résumé


Manindra Agrawal et Somenath Biswas définissent pour le cas des calculs au sens ordinaire, une notion plus forte que la NP-complétude. Par définition, à chaque problème NP-complet X est associé un problème Y, que nous appelons résolution associée à X, qui est P, et tel que x soit dans X si et seulement s'il existe y, de longueur polynomiale en celle de x, tel que (x,y) soit dans Y. Un tel y est appelé solution de x pour X. Si toute résolution R se réduit à Y, de manière à ce que les solutions pour R se déduisent des solutions pour Y, Y sera appelée résolution universelle. Les auteurs montrent ensuite un théorème qui permet de prouver qu'une résolution est universelle. Nous généralisons cette définition et ce théorème aux calculs effectués dans une structure arbitraire, en particulier aux calculs sur les réels définis par Blum, Shub et Smale. Nous étudions ensuite des exemples de telles résolutions, dans des structures réelles, et faisant intervenir par exemple des réseaux neuronaux.

Abstract


Manindra Agrawal and Somenath Biswas define a notion stronger than NP-completeness. With every language X in NP is associated a polynomial-time verifiable binary relation Y, called a resolution, so that x is in X if and only if there exists y, which size is a polynomial function of the size of x, and (x,y) is in Y. Such an y is called a solution of x for X. If Y and Y' are resolutions associated with X and X', a solution-preserving reduction of Y to Y' is a reduction of X to X', so that the solutions of any instance for X can be quickly recovered from the solutions of the image of the instance under the reduction. A resolution Y is called universal if there exists a solution-preserving reduction from every resolution to Y. Then, Manindra Agrawal and Somenath Biswas give a theorem that help us to show that a resolution is universal, without searching for reduction. We generalize this definition and this theorem for languages over an arbitrary structure, and in particular over the reals, as it was defined in by Blum, Shub and Smale. We then study examples with neural networks.