11 December 2001,
Complexity lower bounds for Positivstellensatz proofs
,
D. Grigoriev

Recently an approach to NP-coNP problem based on proof systems using the Nullstellensatz was developed and there were shown complexity lower bounds for the proofs in such systems. In the talk a stronger proof system which relies on the Positivstellensatz is introduced and complexity lower bounds for several problems like the knapsack or the parity principle are established. These results could be also treated independently of the complexity theory as the lower bounds in the Positivstellensatz.

For more information, see http://ssor.twi.tudelft.nl/~dima