Théorème de Schaefer et CSP de largeur illimitée

12

Le théorème de dichotomie de Schaefer montre que chaque problème de CSP sur est soit résoluble en temps polynomial, soit NP-complet. Cela s'applique uniquement aux problèmes CSP de largeur limitée, à l'exclusion de SAT et Horn-SAT, par exemple. Les problèmes CSP généraux de largeur illimitée peuvent être très difficiles (même non calculables), alors limitons-nous aux problèmes qui sont "naturels" et qui sont en NP.{0,1}

Étant donné un problème CSP de largeur illimitée, pour chaque , nous pouvons regarder la restriction du problème aux clauses de largeur jusqu'à k . Le théorème de Schaefer s'applique maintenant, et le problème restreint est soit en P soit en NP-complet. Si pour certains k , le problème k- restreint est NP-complet, alors le problème non restreint l'est aussi. La situation est moins claire quand pour tout k , le problème k- restreint est en P.kkkkkk

Le théorème de dichotomie de Schaefer repose sur quatre (ou plus) algorithmes différents qui résolvent tous les cas faciles. Supposons que pour un problème CSP donné, le problème à restriction est toujours résoluble par l'algorithme A. Il se peut que l'algorithme A puisse également être utilisé pour résoudre le problème sans restriction. Ou il se peut que l'algorithme A ne soit pas un temps polynomial dans le cas sans restriction, et nous ignorons alors la dureté du problème.k

Ce type de problème a-t-il été envisagé? Y a-t-il des exemples dans lesquels nous arrivons à l'endroit «ignorant»?

Yuval Filmus
la source

Réponses:

11

Je prétends que pour un «CSP booléen naturel», si la version k- restreinte est en P pour chaque k , alors la version non restreinte est également en P. Je définirai un «CSP booléen naturel» ci-dessous.

Le théorème de Schaefer déclare que le CSP booléen sur un ensemble fini S de relations est dans P si au moins une des conditions suivantes est satisfaite et il est NP-complet si aucune d'entre elles n'est satisfaite:

  1. Chaque relation dans S (à l'exception de la constante 0) est satisfaite en affectant 1 à toutes ses variables.
  2. Chaque relation dans S (à l'exception de la constante 0) est satisfaite en affectant 0 à toutes ses variables.
  3. Chaque relation dans S est équivalente à une formule 2-CNF.
  4. Chaque relation dans S est équivalente à une formule de clause de Horn.
  5. Chaque relation dans S est équivalente à une formule à double clause de Horn. (Une «formule à double clause Horn» signifie une formule CNF où chaque clause contient au plus un littéral positif.)
  6. Chaque relation dans S est équivalente à une conjonction de clauses affines.

Supposons maintenant que P ≠ NP, et considérons le cas où S est infini. Si la version k restreinte est en P pour chaque k , alors par le théorème de Schaefer, chaque sous-ensemble fini de S satisfait au moins une des six conditions ci-dessus, et cela signifie que l'ensemble S satisfait à au moins une des six conditions. Est-ce à dire que ce CSP sans restriction sur l'arité est également en P? Pas encore.

Lorsque S est infini, nous devons spécifier comment chaque clause de la formule d'entrée est donnée. Nous partons du principe qu'il ya une application surjective de {0,1} * à S , qui spécifie le codage des relations dans S . Un CSP booléen est spécifié en donnant à la fois S et cette fonction de codage.

Notez que dans chacun des cas 3, 4, 5 et 6 ci-dessus, il existe un moyen naturel de représenter des relations satisfaisant à la condition: une formule 2-CNF dans le cas 3, une formule de clause Horn dans le cas 4, etc. Même si une relation est équivalente (disons) à une formule 2-CNF, rien ne garantit a priori que son codage donne un accès facile à la formule 2-CNF qui lui est équivalente.

Maintenant, nous disons qu'un CSP booléen est naturel lorsque sa fonction de codage satisfait les points suivants:

  • Étant donné un codage d'une relation et une affectation à toutes ses variables, le fait que la relation soit satisfaite ou non peut être calculé en temps polynomial. (Remarque: cela garantit que le CSP en question est toujours en NP.)
  • Étant donné un codage d'une relation satisfaisant aux conditions 3, 4, 5 ou 6, sa représentation naturelle telle que spécifiée ci-dessus peut être calculée en temps polynomial.

Ensuite, il est facile de voir que si S satisfait à l'une des six conditions ci-dessus et que le codage pour S satisfait à cette condition de «naturalité», alors nous pouvons appliquer l'algorithme correspondant. L'affirmation que j'ai énoncée au début peut être prouvée en considérant à la fois le cas de P = NP et le cas de P ≠ NP.

Tsuyoshi Ito
la source