Name
Abstract | ||
|---|---|---|
Mundici considered the question of whether the interpolant of two propositional formulas of the form F → G can always have a short circuit description, and showed that if this is the case then every problem in NP ∩ co-NP would have polynomial size circuits. In this note we observe further consequences of the interpolant having short circuit descriptions, namely that UP ⊆ 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. |
Year | Venue | Field |
|---|---|---|
2006 | Circuits, Logic, and Games | Discrete mathematics,Algebra,Polynomial,Of the form,Interpolation,Electronic circuit,Mathematics |
DocType | Citations | PageRank |
Conference | 2 | 0.36 |
References | Authors | |
16 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Uwe Schöning | 1 | 998 | 105.69 |
| Jacobo Torán | 2 | 564 | 49.26 |