On some bandwidth restricted versions of the satisfiability problem of propositional CNF formulas (Q1262855)

A log-bandwidth constrained formula is a CNF formula consisting of the clauses \(C_ 1,C_ 2,...,C_ m\), where no variable (genated or not) can be situated in two clauses \(C_ i\) and \(C_ j\) with \(| i-j| >c\cdot \log_ 2m.\) \textit{B. Monien} and \textit{I. H. Sudborough} [Theor. Comput. Sci. 41, 141-167 (1985; Zbl 0618.68043)] show that the problem of satisfiability of log-bandwidth constrained formulas belongs to P. The complexity of some variants of this problem obtained by weakenings of the log-bandwidth constraints is investigated. Some variants are NP-complete and the proofs consist of reductions from nonstandard models for nondeterministic polynomial time bounded Turing machines, which nevertheless are able to accept some well-known NP-complete problems. The paper is well-written and instructive.