La complétude / la dureté du NP doit-elle être constructive?

Y a-t-il un$L\in {\bf NP}$ avec les propriétés suivantes:

1. On sait que implique P = N P .$L\in {\bf P}$${\bf P}={\bf NP}$

2. Il n'y a pas (connu) polynomiale réduction de Turing (ou un autre N P problème -complete) à L .$SAT$${\bf NP}$$L$

En d'autres termes, si un algorithme polynomial de temps pour implique l'effondrement de N P en P , alors est-il nécessaire que cette "dureté générale" de L pour N P soit en quelque sorte c o n s t r u c t i v e , en ce sens que, disons, S A T doit être réductible en L via une réduction spécifique?$L$${\bf NP}$${\bf P}$$L$${\bf NP}$$constructive$$SAT$$L$

Oui, il existe de tels ensembles, prenez n'importe quel ensemble -intermédiaire (tout ensemble qui est de façon prouvée N P -intermédiaire en supposant P ≠ N P ), par exemple, construisez-en un à partir de SAT en utilisant le théorème de Ladner.$\mathsf{NP}$$\mathsf{NP}$$\mathsf{P}\neq\mathsf{NP}$

Notez que votre doit être considéré comme un problème intermédiaire N P , car il est dans N P mais pas complet pour cela. Notez également que vous présumez que P ≠ N P sinon il n'y a pas de L comme chaque problème non trivial serait complet pour N P si N P = P . De plus, les conditions que vous avez données n'impliquent pas l'exhaustivité, donc la question dans la première partie n'est pas la même que la question sur la constructivité de l'exhaustivité.$L$$\mathsf{NP}$$\mathsf{NP}$$\mathsf{P}\neq\mathsf{NP}$$L$$\mathsf{NP}$$\mathsf{NP}=\mathsf{P}$

En ce qui concerne la question dans le titre, à savoir "la dureté doit-elle être constructive?".$\mathsf{NP}$

La réponse dépend de ce que nous entendons par «constructif». Classiquement, un problème de décision est défini comme étant N P -hard iff$A$$\mathsf{NP}$

ce qui signifie

Et par le théorème de Cook, cela équivaut à

ce qui signifie

Comment rendre cette définition constructive? Cela me semble déjà très constructif. Je suppose que ce que vous voulez demander, c'est si nous pouvons le prouver pour certains sans savoir ce qui est f explicitement. Je ne me souviens pas avoir vu une telle preuve de dureté.$A$$f$

Classiquement, même lorsque nous n'avons pas de fonction spécifique, il y a une fonction, dire qu'il est impossible qu'aucune fonction ne soit une réduction équivaut à dire qu'une fonction est une réduction. Pour parler de constructivité, nous devons être plus prévenants. Par exemple, nous pouvons parler d'énoncés qui peuvent être prouvés de manière classique mais non constructive (par exemple, l'intuitionisme où différents états de connaissances mathématiques ont du sens, Google pour «mathématicien idéal» ou vérifiez cela ).

Intuitivement, il me semble plausible que nous puissions prouver une telle affirmation en utilisant une preuve par contradiction et sans donner de fonction de réduction explicite. Mais cela ne signifie pas qu'il n'y a aucune preuve constructive de la déclaration. Pour dire plus qu'aucune preuve constructive n'existe, nous devons être plus précis: preuves dans quelle théorie / système? qu'entendons-nous par une preuve constructive?

Vous pouvez être intéressé par les ensembles créatifs, inventés dans [1] comme contre-exemple conjecturé à la conjecture de Berman-Hartmanis que tous les ensembles NP-complets sont isomorphes à SAT.$k$

"Isomorphic" est différent d'une réduction de Turing (significativement plus faible en fait), mais ces ensembles se sont révélés être NP-dur directement et pour autant que je sache, il n'y a pas de réduction connue de SAT. Cela dit, selon la définition de l'exhaustivité de NP, il doit y avoir une certaine réduction entre les deux, donc bien que cela réponde au critère de réduction "aucune connue", ce n'est peut-être pas exactement ce que vous recherchez.

[1] Joseph, D. et Young, P. Quelques remarques sur les fonctions des témoins pour les ensembles non polynomiaux et non complets dans NP. Informatique théorique. vol 39, pg 225--237. 1985. Elsevier.

Voici un exemple de la question dans le titre. Il est tiré de l'article suivant: Jan Kratochvil, Petr Savicky et Zsolt Tuza. Une occurrence supplémentaire de variables fait passer la satisfiabilité de trivial à np-complete. SIAM Journal on Computing, 22 (1): 203-210, 1993.

Soit f (k) l'entier maximal r tel que chaque forumula k-SAT dans lequel chaque variable apparaît au plus r fois, soit satisfiable. On ne sait pas si f (k) est calculable, bien que des limites relativement étroites lui soient connues (voir H. Gebauer, R. Moser, D. Scheder et E. Welzl. The Lov ́asz Local Lemma and Satisfiability. Efficient Algorithms, pages 30-54, 2009.).

(k, s) -SAT est le problème k-SAT limité au forumlas dans lequel chaque variable se produit au plus s fois.

Kratochvil et al. a prouvé que (k, f (k) +1) -SAT est NP-complet. Notez que (k, f (k)) - Les problèmes SAT sont toujours satisfaisables (par définition). La réduction elle-même n'est pas constructive: notez que la réduction génère une formule dans laquelle chaque variable se produit au maximum f (k) +1 fois, même si f (k) n'est pas connu pour être calculable. L'idée principale non constructive est que même si la valeur f (k) est inconnue, il existe une formule (k, f (k) +1) -SAT qui n'est pas satisfaisable, et ils manipulent cette formule en fonction de leurs besoins .

Agrawal et Biswas ont présenté un langage NP-complet pour lequel il n'y a pas de réduction connue de Karp ou Cook. La preuve d'exhaustivité suit parce que sa relation témoin est universelle (la relation témoin a les opérateurs de jointure et d'équivalence nécessaires pour être universels). La langue est donnée dans la section 6.3 de la référence.

M.Agrawal, S.Biswas, Universal relations in Proceedings IEEE Conferenceon Structure in Complexity Theory (1992), pp. 207-220.