Instance compression for the polynomial hierarchy and beyond

DOI10.1007/978-3-642-33293-7_13MaRDI QIDQ4899247zbMATH OpenOpenAlexFDO

Authors Chiranjit Chakraborty, Rahul Santhanam

Publication date 7 January 2013

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

Full work available at URL https://www.pure.ed.ac.uk/ws/files/17928375/Chakraborty_Santhanam_2012_Instance_Compression_for_the_Polynomial_Hierachy_and_Beyond.pdf

Mathematics Subject Classification ID

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)

Recommendations

• New limits to classical and quantum instance compression
• Infeasibility of instance compression and succinct PCPs for NP
• On the compressibility of \(\mathcal{NP}\) instances and cryptographic applications
• Some remarks on the incompressibility of width-parameterized SAT instances
• scientific article; zbMATH DE number 3883612

Cited in

(3)

• On the compressibility of \(\mathcal{NP}\) instances and cryptographic applications
• New limits to classical and quantum instance compression
• Infeasibility of instance compression and succinct PCPs for NP

This page was built for publication: Instance compression for the polynomial hierarchy and beyond

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