Some Remarks on the Incompressibility of Width-Parameterized SAT Instances

Compressibility of a formula regards reducing the length of the input, or some other parameter, while preserving the solution. Any 3-

SAT

instance on

N

variables can be represented by

O

(

N

3

) bits; [4] proved that the instance length in general cannot be compressed to

O

(

N

3 − 

ε

) bits under the assumption

$\mathbf{NP}\not\subseteq\mathbf{coNP}$

/poly

, which implies that the polynomial hierarchy does not collapse. This note initiates research on compressibility of

SAT

instances parameterized by width parameters, such as tree-width or path-width. Let

SAT

tw

(

w

(

n

)) be the satisfiability instances of length

n

that are given together with a tree-decomposition of width

O

(

w

(

n

)), and similarly let

SAT

pw

(

w

(

n

)) be instances with a path-decomposition of width

O

(

w

(

n

)). Applying simple techniques and observations, we prove conditional incompressibility for both instance length and width parameters: (i) under the exponential time hypothesis, given an instance

φ

of

SAT

tw

(

w

(

n

)) it is impossible to find within polynomial time a

φ

′ that is satisfiable if and only if

φ

is satisfiable and tree-width of

φ

′ is half of

φ

; and (ii) assuming a scaled version of

$\mathbf{NP}\not\subseteq\mathbf{coNP}$

/poly

, any 3-

SAT

pw

(

w

(

n

)) instance of

N

variables cannot be compressed to

O

(

N

1 − 

ε

) bits.