2026-07-23T10:34:49Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17394 2024-03-06T10:59:38Z ddc:004 open_access

Why MCSP Is a More Important Problem Than SAT (Invited Talk) Santhanam, Rahul Minimum Circuit Size Problem Satisfiability Cryptography Learning Approximation CNF Satisfiability (SAT) and its variants are generally considered the central problems in complexity theory, due to their applications in the theory of NP-completeness, logic, verification, probabilistically checkable proofs and parameterized complexity, among other areas. We challenge this conventional wisdom and argue that analysing the Minimum Circuit Size Problem (MCSP) and its relatives is more important from the perspective of fundamental problems in complexity theory, such as complexity lower bounds, minimal assumptions for cryptography, a robust theory of average-case complexity, and optimal results in hardness of approximation. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Rahul Santhanam 2022 Is Part Of LIPIcs, Volume 250, 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2022.2 urn:nbn:de:0030-drops-173943 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2022.2 eng https://creativecommons.org/licenses/by/4.0/legalcode