On the existence of polynomial time algorithms for interpolation problems in propositional logic.
Elias Dahlhaus, A. Israeli, J. A. Makowsky · Notre Dame Journal of Formal Logic · 1988
On etudie la complexite de differents problemes d'interpolation en logique propositionnelle eventuellement quantifiee. On poursuit les recherches de Mundici et on relie les problemes d'interpolation aux hierarchies de complexites entre espace logarithmique deterministe et espace polynomial deterministe