Monotone Circuit Lower Bounds from Resolution

被引：7

作者：

Garg, Ankit ^{[1
]}

Goos, Mika ^{[2
]}

Kamath, Pritish ^{[3
]}

Sokolov, Dmitry ^{[4
]}

机构：

[1] Microsoft Res India, Bengaluru, Karnataka, India

[2] Ecole Polytech Fed Lausanne, Theory Grp, Lausanne, Switzerland

[3] Toyota Technol Inst Chicago, Chicago, IL USA

[4] KTH Royal Inst Technol, Stockholm, Sweden

来源：

THEORY OF COMPUTING | 2020年 / 16卷

基金：

瑞典研究理事会;

关键词：

circuit complexity; communication complexity; proof complexity; COMMUNICATION; COMPLEXITY; PROOFS; SIZE; HARD;

D O I：

10.4086/toc.2020.v016a013

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

For any unsatisfiable CNF formula F that is hard to refute in the Resolution proof system, we show that a gadget-composed version of F is hard to refute in any proof system whose lines are computed by efficient communication protocols-or, equivalently, that a monotone function associated with F has large monotone circuit complexity. Our result extends to monotone real circuits, which yields new lower bounds for the Cutting Planes proof system.

引用

页数：30

共 56 条

[1]

ALEXANDER A, 1997, MATH PAUL ERDOS, VI, P385, DOI [10.1007/978-3-642-60408-9_28, DOI 10.1007/978-3-642-60408-9_28]

[2] THE MONOTONE CIRCUIT COMPLEXITY OF BOOLEAN FUNCTIONS [J].