Stronger Lower Bounds and Randomness-Hardness Trade-Offs Using Associated Algebraic Complexity Classes

摘要

We associate to each Boolean language complexity class C the algebraic class a.C consisting of families of polynomials {f_n} for which the evaluation problem over the integers is in C. We prove the following lower bound and randomness-to-hardness results: