文章基本信息
- 标题：Sum of Squares Bounds for the Ordering Principle
- 本地全文：下载
- 作者：Aaron Potechin
- 期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
- 电子版ISSN：1868-8969
- 出版年度：2020
- 卷号：169
- 页码：38:1-38:37
- DOI：10.4230/LIPIcs.CCC.2020.38
- 出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
- 摘要：In this paper, we analyze the sum of squares hierarchy (SOS) on the ordering principle on n elements (which has N = Î~(n²) variables). We prove that degree O(â^Snlog(n)) SOS can prove the ordering principle. We then show that this upper bound is essentially tight by proving that for any ε > 0, SOS requires degree Ω(n^(1/2 - ε)) to prove the ordering principle.
- 关键词：sum of squares hierarchy; proof complexity; ordering principle
