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 interpolationArticle

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.

https://doi.org/10.23638/LMCS-16(3:9)2020
Source: arXiv.org:2004.02448
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
Licence: Attribution 4.0 International (CC BY 4.0)

Share and export

Consultation statistics

This page has been seen 2121 times.
This article's PDF has been downloaded 305 times.