Krajíček, Jan - A limitation on the KPT interpolation

lmcs:6267 - Logical Methods in Computer Science, August 12, 2020, Volume 16, Issue 3
A limitation on the KPT interpolation

Authors: Krajíček, Jan

We prove a limitation on a variant of the KPT theorem proposed for propositional proof systems by Pich and Santhanam (2020), for all proof systems that prove the disjointness of two NP sets that are hard to distinguish.

Volume: Volume 16, Issue 3
Published on: August 12, 2020
Submitted on: April 7, 2020
Keywords: Mathematics - Logic,Computer Science - Computational Complexity,03F20, 68Q15,F.4.1


Consultation statistics

This page has been seen 83 times.
This article's PDF has been downloaded 53 times.