Algebraic proof systems over formulas

Dima Grigoriev, Edward A. Hirsch

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

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

תקציר

We introduce two algebraic propositional proof systems ℱ-script N sign script S sign and ℱ-script P sign script C sign. The main difference of our systems from (customary) Nullstellensatz and polynomial calculus is that the polynomials are represented as arbitrary formulas (rather than sums of monomials). Short proofs of Tseitin's tautologies in the constant-depth version of ℱ-script N sign script S sign provide an exponential separation between this system and Polynomial Calculus. We prove that ℱ-script N sign script S sign (and hence ℱ-script P sign script C sign) polynomially simulates Frege systems, and that the constant-depth version of ℱ-script P sign script C sign over finite field polynomially simulates constant-depth Frege systems with modular counting. We also present a short constant-depth ℱ-script P sign script C sign (in fact, ℱ-script N sign script S sign) proof of the propositional pigeon-hole principle. Finally, we introduce several extensions of our systems and pose numerous open questions.

שפה מקוריתאנגלית
עמודים (מ-עד)83-102
מספר עמודים20
כתב עתTheoretical Computer Science
כרך303
מספר גיליון1
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 28 יוני 2003
פורסם באופן חיצוניכן
אירועLogic and Complexity in Computer Science - Creteil, צרפת
משך הזמן: 3 ספט׳ 20015 ספט׳ 2001

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Algebraic proof systems over formulas'. יחד הם יוצרים טביעת אצבע ייחודית.

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