Limits to Efficient Preprocessing
summary
Shows that OR-SAT and AND-SAT do not admit polynomial kernels unless NP ⊆ coNP/poly, and extends the impossibility to randomized and a defined quantum compression. Proof builds an Arthur–Merlin verifier that uses a putative kernel to compress T instances to size ≈ T log T, then samples F1…FT to hide an inserted formula; indistinguishability uses Pinsker and Vajda bounds plus a minimax sampling argument, so the kernel would yield a collapse of complexity classes.
AI-written summary · about