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.