2026-07-25T01:58:08Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5439 2024-03-06T10:36:23Z ddc:004 open_access

Thinking Algorithmically About Impossibility (Invited Talk) Williams, R. Ryan satisfiability derandomization circuit complexity Complexity lower bounds like P != NP assert impossibility results for all possible programs of some restricted form. As there are presently enormous gaps in our lower bound knowledge, a central question on the minds of today's complexity theorists is how will we find better ways to reason about all efficient programs? I argue that some progress can be made by (very deliberately) thinking algorithmically about lower bounds. Slightly more precisely, to prove a lower bound against some class C of programs, we can start by treating C as a set of inputs to another (larger) process, which is intended to perform some basic analysis of programs in C. By carefully studying the algorithmic "meta-analysis" of programs in C, we can learn more about the limitations of the programs being analyzed. This essay is mostly self-contained; scant knowledge is assumed of the reader. Schloss Dagstuhl – Leibniz-Zentrum für Informatik R. Ryan Williams 2015 Is Part Of LIPIcs, Volume 41, 24th EACSL Annual Conference on Computer Science Logic (CSL 2015) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CSL.2015.14 urn:nbn:de:0030-drops-54396 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2015.14 eng https://creativecommons.org/licenses/by/3.0/legalcode