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

lmcs:6267 - Logical Methods in Computer Science, August 12, 2020, Volume 16, Issue 3 - https://doi.org/10.23638/LMCS-16(3:9)2020
A limitation on the KPT interpolation

Authors: Jan Krajíček

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
Accepted on: July 30, 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 207 times.
This article's PDF has been downloaded 106 times.