Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity
| Autor: | Dima Grigoriev |
|---|---|
| Přispěvatelé: | Grigoriev, Dima, Centre National de la Recherche Scientifique (CNRS) |
| Rok vydání: | 2001 |
| Předmět: |
Discrete mathematics
General Computer Science 010102 general mathematics Parity (physics) 0102 computer and information sciences [MATH] Mathematics [math] Mathematical proof 01 natural sciences Upper and lower bounds Algebraic logic Positivstellensatz calculus proofs Theoretical Computer Science Combinatorics 010201 computation theory & mathematics Theory of computing Computer Science::Logic in Computer Science boolean binomial system Calculus [MATH]Mathematics [math] 0101 mathematics Tseitin tautologies Real field Mathematics Computer Science(all) |
| Zdroj: | Theoretical Computer Science Theoretical Computer Science, Elsevier, 2001 |
| ISSN: | 0304-3975 1879-2294 |
| DOI: | 10.1016/s0304-3975(00)00157-2 |
| Popis: | In this paper we establish a linear (thereby, sharp) lower bound on degrees of Positivstellensatz calculus refutations over a real field introduced in Grigoriev and Vorobjov (Ann. Pure Appl. Logic, to appear), for the Tseitin tautologies and for the parity (the mod 2 principle). We use the machinery of the Laurent proofs developed for binomial systems in Buss et al. (Proc. 31st Ann. ACM Symp. on Theory of Computing, 1999, pp. 547–556; J. Comput. Systems Sci., to appear). |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect