2012 | OriginalPaper | Chapter
Some Remarks on the Incompressibility of Width-Parameterized SAT Instances
Author : Bangsheng Tang
Published in: Frontiers in Algorithmics and Algorithmic Aspects in Information and Management
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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.