On the Width of Semialgebraic Proofs and Algorithms

• 成果类型: Article
• 署名作者: Razborov, Alexander
• 署名单位: University of Chicago; University of Chicago; Russian Academy of Sciences; Steklov Mathematical Institute of the Russian Academy of Sciences
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2016.0840
• 发表日期: 2017
• 页码: 1106-1134
• 关键词: cutting-plane proofs; Lower bounds; complexity; RESOLUTION; inequalities; optimization; hierarchy; gaps

摘要

In this paper we study width of semialgebraic proof systems and various cut-based procedures in integer programming. We focus on two important systems: Gomory-Chvatal cutting planes and Lovasz-Schrijver lift-and-project procedures. We develop general methods for proving width lower bounds and apply them to random k-CNFs and several popular combinatorial principles, like the perfect matching principle and Tseitin tautologies. We also show how to apply our methods to various combinatorial optimization problems. We establish a supercritical trade-off between width and rank, that is we give an example in which small width proofs are possible but require exponentially many rounds to perform them.