Réduction facile de 3SAT au problème de chemin hamiltonien

19

Il y a une réduction dans le livre de Sipser "Introduction à la théorie du calcul" à la page 286 de 3SAT au problème de chemin hamiltonien.

Y a-t-il une réduction plus simple?

Par plus simple, je veux dire une réduction qui serait plus facile à comprendre (pour les étudiants).

Y a-t-il une réduction qui utilise un nombre linéaire de variables?

La réduction de Sipser utilise variables où k est le nombre de clauses et n est le nombre de variables. En d'autres termes, il est possible que la réduction fasse sauter la taille de s à O ( s 2 ) . Y a-t-il une réduction simple où la taille de la sortie de la réduction est linéaire dans la taille de son entrée?O(kn)knsO(s2)

Si ce n'est pas possible, y a-t-il une raison? Cela impliquerait-il un résultat inconnu en complexité / algorithmes?

Kaveh
la source
Juste pour être clair: voulez-vous la fonction de réduction qui mappe les instances 3SAT aux instances HP, ou voulez-vous la preuve qui réduit "3SAT dans NPC?" à "HP dans NPC?"? (Je suppose que le premier). Pourriez-vous décrire la preuve à laquelle vous faites référence? Certains d'entre nous pourraient ne pas avoir le livre à portée de main.
Raphael
@Raphael, je veux une réduction de 3SAT à HamPath.
Kaveh
La réduction de Sipser est un gadget utilisé depuis longtemps, je préfère ne pas répéter la réduction ici. Vous pouvez interpréter la première question comme: y a-t-il une réduction simple?
Kaveh
2
@Kaveh Je trouve les diapositives de la conférence ici assez faciles à suivre: cbcb.umd.edu/~carlk/bioinfo-lectures/sat.pdf Ils réduisent 3sat en Ham. Cycle et Ham. Aller à Ham. Chemin. Ils ont été commodément le premier succès pour "la réduction du 3sat au chemin hamiltonien" mais ne répondent probablement pas à votre deuxième question.
Joe
1
@Kaveh: belle question, en particulier le "Cela impliquerait-il un résultat inconnu en complexité / algorithmes?" partie :-). Je ne suis pas un expert, mais j'aimerais qu'il soit demandé sur cstheory.
Vor

Réponses:

7

O(n+k)nk

kn4k4k3kO(n+k)

cc
la source