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: Arteche, N, Khaniki, E, Pich, J, Santhanam, R
פורמט: Conference item
שפה:English
יצא לאור: Schloss Dagstuhl – Leibniz-Zentrum für Informatik 2024