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.

    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 1143 times.
    This article's PDF has been downloaded 177 times.