When quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-9735
Go to the corresponding Portal

Schöning, Uwe ; Torán, Jacobo

A note on the size of Craig Interpolants

06451.ToranJacobo.Paper.973.pdf (0.1 MB)


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.

BibTeX - Entry

  author =	{Uwe Sch{\"o}ning and Jacobo Tor{\'a}n},
  title =	{A note on the size of Craig Interpolants},
  booktitle =	{Circuits, Logic, and Games},
  year =	{2007},
  editor =	{Thomas Schwentick and Denis Th{\'e}rien and Heribert Vollmer },
  number =	{06451},
  series =	{Dagstuhl Seminar Proceedings},
  ISSN =	{1862-4405},
  publisher =	{Internationales Begegnungs- und Forschungszentrum f{\"u}r Informatik (IBFI), Schloss Dagstuhl, Germany},
  address =	{Dagstuhl, Germany},
  URL =		{},
  annote =	{Keywords: Interpolant, non-uniform complexity}

Keywords: Interpolant, non-uniform complexity
Collection: 06451 - Circuits, Logic, and Games
Issue Date: 2007
Date of publication: 23.04.2007

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI