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: | , , , |
|---|---|
| Format: | Conference item |
| Language: | English |
| Published: |
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
2024
|