文章基本信息

标题：How Limited Interaction Hinders Real Communication (and What It Means for Proof and Circuit Complexity)
本地全文：下载
作者：Susanna de Rezende ; Jakob Nordström ; Marc Vinyals 等
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2021
卷号：21
语种：English
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：We obtain the first true size-space trade-offs for the cutting planes proof system, where the upper bounds hold for size and total space for derivations with constant-size coefficients, and the lower bounds apply to length and formula space (i.e., number of inequalities in memory) even for derivations with exponentially large coefficients. These are also the first trade-offs to hold uniformly for resolution, polynomial calculus and cutting planes, thus capturing the main methods of reasoning used in current state-of-the-art SAT solvers. We prove our results by a reduction to communication lower bounds in a round-efficient version of the real communication model of [Krajícek '98], drawing on and extending techniques in [Raz and McKenzie '99] and [Göös et al. '15]. Such lower bounds are in turn established by a reduction to trade-offs between cost and number of rounds in the game of [Dymond and Tompa '85] played on directed acyclic graphs. As a by-product of the techniques developed to show these proof complexity trade-off results, we also obtain a separation between monotone-ACi−1 and monotone-NCi, and an exponential separation between monotone-ACi−1 and monotone-ACi, improving exponentially over the superpolynomial separation in [Raz and McKenzie '99].
关键词：circuit complexity;communication complexity;cutting planes;lifting theorems;Proof Complexity