Semi-algebraic proofs, IPS lower bounds, and the τ-conjecture: Can a natural number be negative?

Yaroslav Alekseev, Dima Grigoriev, Edward A. Hirsch, Iddo Tzameret

פרסום מחקרי: פרק בספר / בדוח / בכנספרסום בספר כנסביקורת עמיתים

9 ציטוטים ‏(Scopus)

תקציר

We introduce the binary value principle which is a simple subset-sum instance expressing that a natural number written in binary cannot be negative, relating it to central problems in proof and algebraic complexity. We prove conditional superpolynomial lower bounds on the Ideal Proof System (IPS) refutation size of this instance, based on a well-known hypothesis by Shub and Smale about the hardness of computing factorials, where IPS is the strong algebraic proof system introduced by Grochow and Pitassi (2018). Conversely, we show that short IPS refutations of this instance bridge the gap between sufficiently strong algebraic and semi-algebraic proof systems. Our results extend to full-fledged IPS the paradigm introduced in Forbes et al. (2016), whereby lower bounds against subsystems of IPS were obtained using restricted algebraic circuit lower bounds, and demonstrate that the binary value principle captures the advantage of semi-algebraic over algebraic reasoning, for sufficiently strong systems. Specifically, we show the following: Conditional IPS lower bounds: The Shub-Smale hypothesis (1995) implies a superpolynomial lower bound on the size of IPS refutations of the binary value principle over the rationals defined as the unsatisfiable linear equation g'i=1n 2i-1xi = -1, for boolean xi's. Further, the related τ-conjecture (1995) implies a superpolynomial lower bound on the size of IPS refutations of a variant of the binary value principle over the ring of rational functions. No prior conditional lower bounds were known for IPS or for apparently much weaker propositional proof systems such as Frege. Algebraic vs. semi-algebraic proofs: Admitting short refutations of the binary value principle is necessary for any algebraic proof system to fully simulate any known semi-algebraic proof system, and for strong enough algebraic proof systems it is also sufficient. In particular, we introduce a very strong proof system that simulates all known semi-algebraic proof systems (and most other known concrete propositional proof systems), under the name Cone Proof System (CPS), as a semi-algebraic analogue of the ideal proof system: CPS establishes the unsatisfiability of collections of polynomial equalities and inequalities over the reals, by representing sum-of-squares proofs (and extensions) as algebraic circuits. We prove that IPS is polynomially equivalent to CPS iff IPS admits polynomial-size refutations of the binary value principle (for the language of systems of equations that have no 0/1-solutions), over both g.,Currency sign and g.,.

שפה מקוריתאנגלית
כותר פרסום המארחSTOC 2020 - Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing
עורכיםKonstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath, Julia Chuzhoy
עמודים54-67
מספר עמודים14
מסת"ב (אלקטרוני)9781450369794
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 8 יוני 2020
פורסם באופן חיצוניכן
אירוע52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020 - Chicago, ארצות הברית
משך הזמן: 22 יוני 202026 יוני 2020

סדרות פרסומים

שםProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (מודפס)0737-8017

כנס

כנס52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020
מדינה/אזורארצות הברית
עירChicago
תקופה22/06/2026/06/20

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Semi-algebraic proofs, IPS lower bounds, and the τ-conjecture: Can a natural number be negative?'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי