From proof complexity to circuit complexity via interactive protocols
<p>Folklore in complexity theory suspects that circuit lower bounds against <strong>NC</strong><sup>1</sup> or <strong>P</strong>/poly, currently out of reach, are a necessary step towards proving strong proof complexity lower bounds for systems like Frege o...
Main Authors: | , , , |
---|---|
פורמט: | Conference item |
שפה: | English |
יצא לאור: |
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
2024
|