Lower Bounds on Hilbert's Nullstellensatz and Propositional Proofs
Publication:4892411
DOI10.1112/plms/s3-73.1.1zbMath0853.03017WikidataQ106785076 ScholiaQ106785076MaRDI QIDQ4892411
Toniann Pitassi, Pavel Pudlák, Russell Impagliazzo, Jan Krajíček, P. W. Beame
Publication date: 5 December 1996
Published in: Proceedings of the London Mathematical Society (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1112/plms/s3-73.1.1
algebraic closure; modular counting principle; Frege proofs; algebraic equations over a field; independence results for counting principles; lower bound on the degrees of polynomials; weak form of Hilbert's Nullstellensatz
68Q25: Analysis of algorithms and problem complexity
03F30: First-order arithmetic and fragments
03B05: Classical propositional logic
03F20: Complexity of proofs
Related Items