Une version «locale» est-elle du NP-dur 3-SAT?

Question

Vous trouverez ci-dessous ma simplification d'une partie d'un projet de recherche plus large sur les réseaux bayésiens spatiaux:

Dire qu'une variable est "$ k $-Local "dans une chaîne $ C in 3 text {-cnf} $ S'il y a moins que $ k $ clauses entre la première et la dernière clause dans laquelle il apparaît (où $ k $ est un nombre naturel).

Considérez maintenant le sous-ensemble $ (3, k) text {-lsat} subseseq 3 text {-sat} $ défini par le critère qui pour tout $ C in (3, k) text {-lsat} $, chaque variable dans $ C $ est $ k $-local. Pour quelle raison $ k $ (le cas échéant) est $ (3, k) text {-lsat} $ NP-dur?

---

Voici ce que j'ai considéré jusqu'à présent:

(1) des variations sur la méthode pour montrer que $ 2 text {-sat} $ est en p en réécrivant chaque disjonction comme une implication et en examinant les chemins dirigés sur le graphique dirigé de ces implications (noté ici et présenté en détail aux pp. 184-185 de Papadimitriou's Complexité informatique). Contrairement à $ 2 text {-sat} $, il y a une branche des chemins dirigés dans $ (3, k) text {-lsat} $, mais peut-être que le nombre de chemins dirigés est limité par les contraintes spatiales sur les variables. Pas de succès avec cela jusqu'à présent.

(2) une réduction du temps polynomial de $ 3 text {-sat} $ (ou tout autre problème de NP-complete connu) pour $ (3, k) text {-lsat} $. Par exemple, j'ai essayé divers schémas d'introduction de nouvelles variables. Cependant, rassembler les clauses qui contiennent la variable d'origine $ x_k $ Généralement, je traîne des «chaînes» de clauses supplémentaires contenant les nouvelles variables et celles-ci interfèrent avec les contraintes spatiales sur les autres variables.

Je ne suis sûrement pas dans un nouveau territoire ici. Y a-t-il un problème NP-durs connu qui peut être réduit à $ (3, k) text {-lsat} $ Ou les contraintes spatiales empêchent-elles le problème d'être aussi difficile?