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