Classification of the asymptotic Proof Complexity of Polynomial Calculus

dc.contributor.author	RIIS, SM
dc.date.accessioned	2019-08-16T13:06:42Z
dc.date.available	2019-08-16T13:06:42Z
dc.date.issued	2008
dc.identifier.issn	0911-0119
dc.identifier.uri	https://qmro.qmul.ac.uk/xmlui/handle/123456789/59178
dc.description.abstract	We show that the asymptotic complexity of uniformly generated (expressible in First-Order (FO) logic) propositional tautologies for the Nullstellensatz proof system (NS) as well as for Polynomial Calculus, (PC) has four distinct types of asymptotic behavior over fields of finite characteristic. More precisely, based on some highly non-trivial work by Krajicek, we show that for each prime p there exists a function l(n) ∈ Ω(log(n)) for NS and l(n) ∈ Ω(log(log(n)) for PC, such that the propositional translation of any FO formula (that fails in all finite models), has degree proof complexity over fields of characteristic p, that behave in 4 mutually distinct ways	en_US
dc.publisher	Springer	en_US
dc.relation.ispartof	Graphs and Combinatorics
dc.title	Classification of the asymptotic Proof Complexity of Polynomial Calculus	en_US
dc.type	Article	en_US
dc.rights.holder	© 2008 IEEE
pubs.notes	Not known	en_US
rioxxterms.funder	Default funder	en_US
rioxxterms.identifier.project	Default project	en_US