License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/DagSemProc.06451.3
URN: urn:nbn:de:0030-drops-9735
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2007/973/
Go to the corresponding Portal

Schöning, Uwe ; Torán, Jacobo

A note on the size of Craig Interpolants

pdf-format:
06451.ToranJacobo.Paper.973.pdf (0.1 MB)

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{schoning_et_al:DagSemProc.06451.3,
  author =	{Sch\"{o}ning, Uwe and Tor\'{a}n, Jacobo},
  title =	{{A note on the size of Craig Interpolants}},
  booktitle =	{Circuits, Logic, and Games},
  pages =	{1--9},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{6451},
  editor =	{Thomas Schwentick and Denis Th\'{e}rien and Heribert Vollmer},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2007/973},
  URN =		{urn:nbn:de:0030-drops-9735},
  doi =		{10.4230/DagSemProc.06451.3},
  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