Infeasibility of instance compression and succinct PCPs for NP
From MaRDI portal
Publication:619903
Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)
A question by \textit{H. L. Bodlaender, R. G. Downey, M. R. Fellows} and \textit{D. Hermelin} [``On problems without polynomial kernels, J. Comput. Syst. Sci. 75, No. 8, 423--434 (2009; Zbl 1192.68288)] asks if there is a polynomial-time computable function that, given a sequence of \(m\) Boolean formulae each of length at most \(n\), computes a formula of length bounded by a polynomial in \(n\) such that the computed formula is satisfiable if and only if at least one of the given formulae is satisfiable. This paper settles the question in the negative, under the assumption that the polynomial-time hierarchy does not collapse. A number of consequences of this result, the maybe most prominent of which concerns kernalizability of certain graph problems, are shown.
Recommendations
Cites work
- Advice classes of parametrized tractability
- Conditionally-perfect secrecy and a provably-secure randomized cipher
- Constructing locally computable extractors and cryptosystems in the bounded-storage model
- Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses
- scientific article; zbMATH DE number 5485524 (Why is no real title available?)
- scientific article; zbMATH DE number 3593565 (Why is no real title available?)
- scientific article; zbMATH DE number 1303133 (Why is no real title available?)
- scientific article; zbMATH DE number 1507224 (Why is no real title available?)
- scientific article; zbMATH DE number 1559537 (Why is no real title available?)
- scientific article; zbMATH DE number 2086371 (Why is no real title available?)
- scientific article; zbMATH DE number 1418287 (Why is no real title available?)
- scientific article; zbMATH DE number 2234775 (Why is no real title available?)
- Interactive PCP
- Lower bounds for kernelizations and other preprocessing procedures
- On Everlasting Security in the Hybrid Bounded Storage Model
- On Problems without Polynomial Kernels (Extended Abstract)
- On the compressibility of \(\mathcal{NP}\) instances and cryptographic applications
- On the randomness complexity of efficient sampling
- Parametrized complexity theory.
- Probabilistic checking of proofs
- Proof verification and the hardness of approximation problems
- Simple extractors for all min-entropies and a new pseudorandom generator
- Some consequences of non-uniform conditions on uniform classes
- Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
- The complexity of theorem-proving procedures
- The PCP theorem by gap amplification
- The probabilistic method. With an appendix on the life and work of Paul Erdős.
- Turing machines that take advice
Cited in
(only showing first 100 items - show all)- Polynomial-time compression
- Two edge modification problems without polynomial kernels
- Multivariate complexity analysis of geometric \textsc{Red Blue Set Cover}
- On the kernelization complexity of string problems
- Parameterized algorithms for Max Colorable Induced Subgraph problem on perfect graphs
- Parameterized computational complexity of finding small-diameter subgraphs
- On the (non-)existence of polynomial kernels for \(P _{l }\)-free edge modification problems
- On the parameterized complexity of contraction to generalization of trees
- On the approximate compressibility of connected vertex cover
- Finding cuts of bounded degree: complexity, FPT and exact algorithms, and kernelization
- On the parametrized complexity of read-once refutations in UTVPI+ constraint systems
- On some FPT problems without polynomial Turing compressions
- A polynomial kernel for bipartite permutation vertex deletion
- Introducing \textsf{lop}-kernels: a framework for kernelization lower bounds
- Polynomial kernels for hitting forbidden minors under structural parameterizations
- Kernels for packing and covering problems
- Two edge-disjoint paths with length constraints
- Kernelization lower bound for permutation pattern matching
- Backdoors to tractable answer set programming
- A completeness theory for polynomial (Turing) kernelization
- Incompressibility of \(H\)-free edge modification problems
- Sparsification upper and lower bounds for graph problems and not-all-equal SAT
- Tractability, hardness, and kernelization lower bound for and/or graph solution
- Polynomial kernelizations for MIN \(F^{+}\Pi _{1}\) and MAX NP
- On the hardness of losing width
- A Turing kernelization dichotomy for structural parameterizations of \(\mathcal{F} \)-minor-free deletion
- Preprocessing to reduce the search space: antler structures for feedback vertex set
- Building large \(k\)-cores from sparse graphs
- FPT and kernelization algorithms for the induced tree problem
- A multistage view on 2-satisfiability
- On polynomial kernels for sparse integer linear programs
- FPT is characterized by useful obstruction sets: connecting algorithms, kernels, and quasi-orders
- Kernel lower bounds using co-nondeterminism: finding induced hereditary subgraphs
- On polynomial kernels for structural parameterizations of odd cycle transversal
- Kernel bounds for path and cycle problems
- Some remarks on the incompressibility of width-parameterized SAT instances
- A basic parameterized complexity primer
- Studies in Computational Aspects of Voting
- Clique Cover and Graph Separation
- Parameterized complexity dichotomy for \textsc{Steiner Multicut}
- Complexity with Rod
- Incompressible functions, relative-error extractors, and the power of nondeterministic reductions
- On the compressibility of \(\mathcal{NP}\) instances and cryptographic applications
- Efficient Probabilistically Checkable Debates
- Kernelization of cycle packing with relaxed disjointness constraints
- Finding two edge-disjoint paths with length constraints
- Vertex cover structural parameterization revisited
- Monotonic reductions, representative equivalence, and compilation of intractable problems
- Algorithms and kernels for \textsc{Feedback Set} problems in generalizations of tournaments
- New limits to classical and quantum instance compression
- Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter
- Preprocessing subgraph and minor problems: when does a small vertex cover help?
- Incremental list coloring of graphs, parameterized by conservation
- Kernel bounds for path and cycle problems
- Parameterized complexity of vertex deletion into perfect graph classes
- Data reduction for graph coloring problems
- On the parameterized complexity of the repetition free longest common subsequence problem
- Fractals for kernelization lower bounds
- Confronting intractability via parameters
- The kernelization complexity of connected domination in graphs with (no) small cycles
- On cutwidth parameterized by vertex cover
- Instance compression for the polynomial hierarchy and beyond
- Succinct Permanent Is NEXP-Hard with Many Hard Instances
- Restricted and swap common superstring: a multivariate algorithmic perspective
- On the parameterized complexity of finding separators with non-hereditary properties
- Dual parameterization of weighted coloring
- Polynomial Kernels for Hitting Forbidden Minors under Structural Parameterizations.
- Solving partition problems almost always requires pushing many vertices around
- Hans Bodlaender and the Theory of Kernelization Lower Bounds
- Algorithms, Complexity, and Hans
- Crossing Paths with Hans Bodlaender: A Personal View on Cross-Composition for Sparsification Lower Bounds
- An approximate kernel for connected feedback vertex set
- Fixed-parameter algorithms for DAG partitioning
- On kernelization for edge dominating set under structural parameters
- A deterministic polynomial kernel for odd cycle transversal and vertex multiway cut in planar graphs
- Data-compression for parametrized counting problems on sparse graphs
- On the Complexity of Bounded Context Switching.
- How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs?
- A Deterministic Polynomial Kernel for Odd Cycle Transversal and Vertex Multiway Cut in Planar Graphs
- On making a distinguished vertex of minimum degree by vertex deletion
- Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
- Partially polynomial kernels for set cover and test cover
- Compression via matroids: a randomized polynomial kernel for odd cycle transversal
- Co-nondeterminism in compositions: a kernelization lower bound for a Ramsey-type problem
- Approximate Turing Kernelization for Problems Parameterized by Treewidth
- Fine-grained complexity of safety verification
- Polynomial Kernel for Interval Vertex Deletion
- Multistage \(s-t\) path: confronting similarity with dissimilarity
- Succinct interactive oracle proofs: applications and limitations
- Kernel bounds for disjoint cycles and disjoint paths
- Indistinguishability obfuscation, range avoidance, and bounded arithmetic
- Preprocessing to reduce the search space: antler structures for feedback vertex set
- Minimum separator reconfiguration
- Twin-width. III: Max independent set, min dominating set, and coloring
- Zero-knowledge IOPs approaching witness length
- Lossy planarization: a constant-factor approximate kernelization for planar vertex deletion
- On quasipolynomial multicut-mimicking networks and kernelization of multiway cut problems
- No polynomial kernels for knapsack
- Kernelization dichotomies for hitting subgraphs under structural parameterizations
- Parameterized algorithms for locating-dominating sets
This page was built for publication: Infeasibility of instance compression and succinct PCPs for NP
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q619903)
