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

AbstractIn the present paper we study the complexity of some restricted versions of the satisfiability problem for propositional CNF formulas. We define these restrictions through their corresponding languages which are identified using the self-reducibility property of satisfiable propositional CNF formulas. The notion of kernel constructibility (similar to self-reducibility) and that of bandwidth are used to define these languages. The results throw some light on the structure of the satisfiability problem. The proof methods illustrate the application of a certain method for reducing Turing machine acceptance problems to decision problems for logics