A Lower Bound for Polynomial Calculus with Extension Rule

Yaroslav Alekseev

In this paper we study an extension of the Polynomial Calculus proof system where we can introduce new variables and take a square root. We prove that an instance of the subset-sum…