License
when quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-9735
URL: http://drops.dagstuhl.de/opus/volltexte/2007/973/
Schöning, Uwe ; Torán, Jacobo

A note on the size of Craig Interpolants

pdf-format:
Dokument 1.pdf (143 KB)

Abstract

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

@InProceedings{schning_et_al:DSP:2007:973,
  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 =		{http://drops.dagstuhl.de/opus/volltexte/2007/973},
  annote =	{Keywords: Interpolant, non-uniform complexity}
}

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

DROPS-Home | Fulltext Search | Imprint Published by LZI