Complexity of null- and Positivstellensatz proofs


Grigoriev, D. and Vorobjov, N., 2002. Complexity of null- and Positivstellensatz proofs. Annals of Pure and Applied Logic, 113 (1-3), pp. 153-160.

Related documents:

This repository does not currently have the full-text of this item.
You may be able to access a copy if URLs are provided below.


We introduce two versions of proof systems dealing with systems of inequalities: Positivstellensatz refutations and Positivstellensatz calculus. For both systems we prove the lower bounds on degrees and lengths of derivations for the example due to Lazard, Mora and Philippon. These bounds are sharp, as well as they are for the Nullstellensatz refutations and for the polynomial calculus. The bounds demonstrate a gap between the Null- and Positivstellensatz refutations on one hand, and the polynomial calculus and Positivstellensatz calculus on the other. (C) 2002 Elsevier Science B.V. All rights reserved.


Item Type Articles
CreatorsGrigoriev, D.and Vorobjov, N.
DepartmentsFaculty of Science > Computer Science
ID Code5581
Additional InformationID number: ISI:000173582300009


Actions (login required)

View Item