AND-compression of NP-complete problems: streamlined proof and minor observations

DOI10.1007/978-3-319-13524-3_16zbMATH Open1350.68118arXiv1405.4472OpenAlexW3100910790MaRDI QIDQ309801FDOQ309801

Authors: Holger Dell 

Publication date: 7 September 2016

Published in: Algorithmica, Parameterized and Exact Computation (Search for Journal in Brave)

Abstract: Drucker (2012) proved the following result: Unless the unlikely complexity-theoretic collapse coNP is in NP/poly occurs, there is no AND-compression for SAT. The result has implications for the compressibility and kernelizability of a whole range of NP-complete parameterized problems. We present a streamlined proof of Drucker's theorem. An AND-compression is a deterministic polynomial-time algorithm that maps a set of SAT-instances $x_1,dots,x_t$ to a single SAT-instance $y$ of size poly(max $|x_i|$) such that $y$ is satisfiable if and only if all $x_i$ are satisfiable. The "AND" in the name stems from the fact that the predicate "$y$ is satisfiable" can be written as the AND of all predicates "$x_i$ is satisfiable". Drucker's result complements the result by Bodlaender et al. (2009) and Fortnow and Santhanam (2010), who proved the analogous statement for OR-compressions, and Drucker's proof not only subsumes that result but also extends it to randomized compression algorithms that are allowed to have a certain probability of failure. Drucker (2012) presented two proofs: The first uses information theory and the minimax theorem from game theory, and the second is an elementary, iterative proof that is not as general. In our proof, we realize the iterative structure as a generalization of the arguments of Ko (1983) for P-selective sets, which use the fact that tournaments have dominating sets of logarithmic size. We generalize this fact to hypergraph tournaments. Our proof achieves the full generality of Drucker's theorem, avoids the minimax theorem, and restricts the use of information theory to a single, intuitive lemma about the average noise sensitivity of compressive maps. To prove this lemma, we use the same information-theoretic inequalities as Drucker.

Full work available at URL: https://arxiv.org/abs/1405.4472

Recommendations

• AND-compression of NP-complete problems: streamlined proof and minor observations
• Proof compression and NP versus PSPACE
• Proof compression and NP versus PSPACE. II
• On the compressibility of \(\mathcal{NP}\) instances and cryptographic applications
• Iterative Compression for Exactly Solving NP-Hard Minimization Problems
• Infeasibility of instance compression and succinct PCPs for NP
• scientific article; zbMATH DE number 915981
• P-complete problems in data compression
• The complexity of some complementation problems
• Approximability of minimum AND-circuits

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Measures of information, entropy (94A17) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Quantum algorithms and complexity in the theory of computing (68Q12) Hypergraphs (05C65)

Cites Work

• Title not available (Why is that?)
• On the compressibility of \(\mathcal{NP}\) instances and cryptographic applications
• Computational Complexity
• On problems without polynomial kernels
• Kernelization Lower Bounds by Cross-Composition
• Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
• Infeasibility of instance compression and succinct PCPs for NP
• Refinements of Pinsker's inequality
• New limits to classical and quantum instance compression
• On self-reducibility and weak P-selectivity
• On the complexity of computational problems regarding distributions
• A complete problem for statistical zero knowledge
• Is Valiant-Vazirani's isolation probability improvable?
• Point line cover: the easy kernel is essentially tight
• Kernelization of packing problems
• Title not available (Why is that?)
• Co-nondeterminism in compositions: a kernelization lower bound for a Ramsey-type problem

Cited In (6)

• AND-compression of NP-complete problems: streamlined proof and minor observations
• New limits to classical and quantum instance compression
• On the (parameterized) complexity of recognizing well-covered \((r,\ell)\)-graphs
• Title not available (Why is that?)
• Kernels for packing and covering problems
• \textsc{ToTo}: an open database for computation, storage and retrieval of tree decompositions

This page was built for publication: AND-compression of NP-complete problems: streamlined proof and minor observations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q309801)