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 ... more >>>

The semantics of decision problems are always essentially independent of the underlying representation. Thus the space of input data (under appropriate indexing) is closed under action of the symmetrical group $S_n$ (for a specific data-size) and the input-output relation is closed under the action of $S_n$. We show that symmetries ... more >>>