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

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)$$k$$n$$s$$O(s^2)$

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

$O(n+k)$$n$$k$

$k$$n$$4k$$4k$$3k$$O(n+k)$