AND-compression of NP-complete problems: streamlined proof and minor observations
From MaRDI portal
Publication:309801
DOI10.1007/s00453-015-0110-yzbMath1350.68118arXiv1405.4472OpenAlexW3100910790MaRDI QIDQ309801
Publication date: 7 September 2016
Published in: Algorithmica, Parameterized and Exact Computation (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1405.4472
Analysis of algorithms and problem complexity (68Q25) Hypergraphs (05C65) 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)
Related Items
New Limits to Classical and Quantum Instance Compression, On the (Parameterized) Complexity of Recognizing Well-Covered $$(r,\ell )$$ -graphs, \textsc{ToTo}: an open database for computation, storage and retrieval of tree decompositions, Kernels for packing and covering problems, Unnamed Item
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Is Valiant-Vazirani's isolation probability improvable?
- Infeasibility of instance compression and succinct PCPs for NP
- On problems without polynomial kernels
- On self-reducibility and weak P-selectivity
- On the Compressibility of $\mathcal{NP}$ Instances and Cryptographic Applications
- On the Complexity of Computational Problems Regarding Distributions
- New Limits to Classical and Quantum Instance Compression
- A complete problem for statistical zero knowledge
- Refinements of Pinsker's inequality
- Kernelization Lower Bounds by Cross-Composition
- Computational Complexity
- Point Line Cover: The Easy Kernel is Essentially Tight
- Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses
