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

✍ Scribed by Natacha Portier

• Publisher: Elsevier Science
• Year: 1998
• Tongue: English
• Weight: 948 KB
• Volume: 201
• Category: Article
• ISSN: 0304-3975
• DOI: 10.1016/s0304-3975(97)00029-7

✦ Synopsis

Agrawal and Biswas (1992) define a notion stronger than NP-completeness.

With every language X in NT' is associated a polynomial-time verifiable binary relation Y, called a resolution, so that f is in X if and only if there exists j, which size is a polynomial function of the size -of X, and (x, y) is in Y. Such an j is called a solution of 2 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 by . We then study examples with neural networks.