Some remarks on the incompressibility of width-parameterized SAT instances

DOI10.1007/978-3-642-29700-7_18zbMATH Open1304.68082OpenAlexW189831120MaRDI QIDQ2897994FDOQ2897994

Authors: Bang-Sheng Tang 

Publication date: 16 July 2012

Published in: Frontiers in Algorithmics and Algorithmic Aspects in Information and Management (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-29700-7_18

Recommendations

• A note on width-parameterized SAT: an exact machine-model characterization
• Infeasibility of instance compression and succinct PCPs for NP
• Theory and Applications of Satisfiability Testing
• Width-parametrized SAT: time-space tradeoffs
• New limits to classical and quantum instance compression

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cited In (6)

• Instance compression for the polynomial hierarchy and beyond
• Infeasibility of instance compression and succinct PCPs for NP
• New width parameters for SAT and \#SAT
• A note on width-parameterized SAT: an exact machine-model characterization
• On the equivalence among problems of bounded width
• Resolution cannot polynomially simulate compressed-BFS

This page was built for publication: Some remarks on the incompressibility of width-parameterized SAT instances

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