Unsolvable systems of equations and proof complexity
type: Item
instance of: scholarly article
title: Unsolvable systems of equations and proof complexity
zbMATH Open document ID: 0903.03033
author: Toniann Pitassi
published in: Documenta Mathematica
publication date: 1998-08-05T00:00:00Z
full work available at URL: https://eudml.org/doc/232165
full work available at URL: Pitassi.MAN.html
review text: This is a survey of an algebraic approach to the efficiency of propositional proof systems. To a formula \(C\) in conjunctive normal form, one associates a set of polynomials \(Q_i\). (An atom \(p\) goes to \(1-y\), \(\neg p\) to \(y\), and \(\vee\) is replaced by \(x\). Thus each conjunct results in a polynomial. And, add \(y^2-y\) to confine the values to \(0\) and \(1\).) The given \(C\) is refutable iff the \(Q_i\)'s have no \(0/1\) solution iff, by the Nullstellensatz, \(\sum P_iQ_i= 1\) for some \(P_i\)'s. According to the author, ``Algebraic proof systems are appealing because of their simplicity and non-syntactic nature'' -- and, of course, much work has been done by algebraists on equations, the Nullstellensatz, etc. She compares algebraic proofs to Frege, resolution systems, etc., and talks about some methods and results (e.g., the design method, lower bounds for pigeonhole principles). The author gives good directions for future work by citing and commenting on open problems. We have also a recent good survey article by \textit{A. Urquhart} about ``The complexity of propositional proofs'' [Bull. Symb. Log. 1, No. 4, 425-467 (1995; Zbl 0845.03025)]. Compared to it, the present article is more research oriented in a narrowly focused area.
Mathematics Subject Classification ID: 03F20
Mathematics Subject Classification ID: 03B05
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 1184383
zbMATH Keywords: propositional proof complexity
zbMATH Keywords: system of equations
zbMATH Keywords: survey
zbMATH Keywords: algebraic approach to the efficiency of propositional proof systems
MaRDI profile type: Publication
Recommended article: Q4353563
Recommended article: Q3081620
Recommended article: Q4790400
Recommended article: Complexity of Propositional Proofs
Recommended article: Algebraic proof systems over formulas.
Recommended article: Q3743300
Recommended article: Counting proofs in propositional logic
Recommended article: Q5290079
Recommended article: Q4273485
Recommended article: Polynomial size proofs of the propositional pigeonhole principle
description: scientific article; zbMATH DE number 1184383