Infeasibility of instance compression and succinct PCPs for NP

DOI10.1016/j.jcss.2010.06.007zbMath1233.68144OpenAlexW1998964055MaRDI QIDQ619903

Publication date: 18 January 2011

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2010.06.007

zbMATH Keywords

satisfiability problem compressibility parameterized complexity probabilistically checkable proof

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

On polynomial kernels for sparse integer linear programs, On Polynomial Kernels for Structural Parameterizations of Odd Cycle Transversal, Kernel Bounds for Path and Cycle Problems, 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, Parameterized complexity dichotomy for \textsc{Steiner Multicut}, New Limits to Classical and Quantum Instance Compression, Incompressible functions, relative-error extractors, and the power of nondeterministic reductions, Kernelization of Cycle Packing with Relaxed Disjointness Constraints, AND-compression of NP-complete problems: streamlined proof and minor observations, A Basic Parameterized Complexity Primer, Studies in Computational Aspects of Voting, Finding Two Edge-Disjoint Paths with Length Constraints, Vertex Cover Structural Parameterization Revisited, Algorithms and kernels for \textsc{Feedback Set} problems in generalizations of tournaments, Two edge modification problems without polynomial kernels, A Turing kernelization dichotomy for structural parameterizations of \(\mathcal{F} \)-minor-free deletion, Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter, Sparsification upper and lower bounds for graph problems and not-all-equal SAT, Tractability, hardness, and kernelization lower bound for and/or graph solution, Clique Cover and Graph Separation, Preprocessing subgraph and minor problems: when does a small vertex cover help?, Multivariate complexity analysis of geometric \textsc{Red Blue Set Cover}, Incremental list coloring of graphs, parameterized by conservation, Preprocessing to reduce the search space: antler structures for feedback vertex set, Kernel bounds for path and cycle problems, Parameterized complexity of vertex deletion into perfect graph classes, Data reduction for graph coloring problems, Building large \(k\)-cores from sparse graphs, Polynomial Kernel for Interval Vertex Deletion, Meta-kernelization with structural parameters, Multistage \(s-t\) path: confronting similarity with dissimilarity, On the parameterized complexity of the repetition free longest common subsequence problem, Succinct interactive oracle proofs: applications and limitations, Polynomial kernelizations for MIN \(F^{+}\Pi _{1}\) and MAX NP, Polynomial kernels for hitting forbidden minors under structural parameterizations, FPT and kernelization algorithms for the induced tree problem, A multistage view on 2-satisfiability, Unnamed Item, On the (non-)existence of polynomial kernels for \(P _{l }\)-free edge modification problems, Parameterized two-player Nash equilibrium, Complexity with Rod, Kernel bounds for disjoint cycles and disjoint paths, Fractals for Kernelization Lower Bounds, On the hardness of losing width, Contracting graphs to paths and trees, Confronting intractability via parameters, The kernelization complexity of connected domination in graphs with (no) small cycles, On cutwidth parameterized by vertex cover, Approximate Turing Kernelization for Problems Parameterized by Treewidth, 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., Fixed-parameter algorithms for DAG partitioning, On the kernelization complexity of string problems, A Deterministic Polynomial Kernel for Odd Cycle Transversal and Vertex Multiway Cut in Planar Graphs, Parameterized algorithms for Max Colorable Induced Subgraph problem on perfect graphs, On making a distinguished vertex of minimum degree by vertex deletion, On the parameterized complexity of contraction to generalization of trees, Parameterized computational complexity of finding small-diameter subgraphs, On the approximate compressibility of connected vertex cover, Partially Polynomial Kernels for Set Cover and Test Cover, Unnamed Item, Kernelization hardness of connectivity problems in \(d\)-degenerate graphs, Kernels for packing and covering problems, Unnamed Item, Unnamed Item, Structural parameterizations of undirected feedback vertex set: FPT algorithms and kernelization, Finding cuts of bounded degree: complexity, FPT and exact algorithms, and kernelization, Turing kernelization for finding long paths and cycles in restricted graph classes, Fine-grained complexity of safety verification, On the parametrized complexity of Read-once refutations in UTVPI+ constraint systems, Efficient Probabilistically Checkable Debates, A deterministic polynomial kernel for odd cycle transversal and vertex multiway cut in planar graphs, FPT is characterized by useful obstruction sets, Kernel Lower Bounds using Co-Nondeterminism: Finding Induced Hereditary Subgraphs, On some FPT problems without polynomial Turing compressions, How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs, On the Complexity of Bounded Context Switching., Two edge-disjoint paths with length constraints, Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses, Dual parameterization of weighted coloring, A polynomial kernel for bipartite permutation vertex deletion, Introducing \textsf{lop}-kernels: a framework for kernelization lower bounds, Kernelization lower bound for permutation pattern matching, Backdoors to tractable answer set programming, Unnamed Item, Unnamed Item, A completeness theory for polynomial (Turing) kernelization, Incompressibility of \(H\)-free edge modification problems

Cites Work