2026-07-21T03:09:06Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:973 2024-03-06T11:07:09Z ddc:004 open_access

A note on the size of Craig Interpolants Schöning, Uwe Torán, Jacobo Interpolant non-uniform complexity Mundici considered the question of whether the interpolant of two propositional formulas of the form $F ightarrow G$ can always have a short circuit description, and showed that if this is the case then every problem in NP $cap$ co-NP would have polynomial size circuits. In this note we observe further consequences of the interpolant having short circuit descriptions, namely that UP $subseteq$ P$/$poly, and that every single valued NP function has a total extension in FP$/$poly. We also relate this question with other Complexity Theory assumptions. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Uwe Schöning and Jacobo Torán 2007 Is Part Of Dagstuhl Seminar Proceedings, Volume 6451, Circuits, Logic, and Games (2007) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/DagSemProc.06451.3 urn:nbn:de:0030-drops-9735 https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06451.3 eng https://creativecommons.org/licenses/by/4.0/legalcode