Some Remarks on the Incompressibility of Width-Parameterized SAT Instances

Abstract. Compressibility regards the reduction the length of the input, or of some other parameter, preserving the solution. Any 3-SAT instance on N vari-ables can be represented by O(N3) bits. [4] proved that the instance length in general cannot be compressed to O(N3−!) bits under the assumption NP!⊆ coNP/poly, which implies that the polynomial hierarchy collapses. This note initiates and puts forward the research on compressibility of SAT instances pa-rameterized by width parameters, such as tree-width, path-width. LetSATtw(w(n)) (SATpw(w(n))) be the satisfiability problem where instances are given together with a tree(path)-decomposition of width O(w(n)), where n is instance length. Based on simple techniques and observations, we prove forSATtw(w(n)) (SATpw(w(n))) conditional incompressibility of both instance length and parameter: (i) under ex-ponential time hypothesis, given an instance φ of SATtw(w(n)) it is impossible to find the φ ′ within polynomial time, such that φ is satisfiable if and only if φ′ is satisfiable, and tree-width of φ ′ is half of φ; and (ii) assuming a scaled version ofNP! ⊆ coNP/poly, any 3-SATpw(w(n)) instance of N variables cannot be compressed to O(N1−!) bits.