|
Trudy Matematicheskogo Instituta imeni V.A. Steklova, 2003, Volume 242, Pages 23–43
(Mi tm403)
|
|
|
|
This article is cited in 23 scientific papers (total in 23 papers)
Lower Bounds for Polynomial Calculus: Nonbinomial Case
M. V. Alekhnovicha, A. A. Razborovb a M. V. Lomonosov Moscow State University
b Steklov Mathematical Institute, Russian Academy of Sciences
Abstract:
We generalize recent linear lower bounds for Polynomial Calculus based on binomial ideals. We produce a general hardness criterion (that we call immunity), which is satisfied by a random function, and prove linear lower bounds on the degree of PC refutations for a wide class of tautologies based on immune functions. As applications of our techniques, we introduce mod$_p$. Tseitin tautologies in the Boolean case (e.g. in the presence of axioms $x_i^2=x_i$), prove that they are hard for PC over fields with characteristic different from $p$, and generalize them to the flow tautologies that are based on the majority function and are proved to be hard over any field. We also prove the $\Omega(n)$ lower bound for random $k$-CNFs over fields of characteristic 2.
Received in October 2002
Citation:
M. V. Alekhnovich, A. A. Razborov, “Lower Bounds for Polynomial Calculus: Nonbinomial Case”, Mathematical logic and algebra, Collected papers. Dedicated to the 100th birthday of academician Petr Sergeevich Novikov, Trudy Mat. Inst. Steklova, 242, Nauka, MAIK «Nauka/Inteperiodika», M., 2003, 23–43; Proc. Steklov Inst. Math., 242 (2003), 18–35
Linking options:
https://www.mathnet.ru/eng/tm403 https://www.mathnet.ru/eng/tm/v242/p23
|
Statistics & downloads: |
Abstract page: | 577 | Full-text PDF : | 157 | References: | 48 |
|