| ชื่อเรื่อง | : | Exponential lower bound for static semi-algebraic proofs. |
| นักวิจัย | : | Grigoriev, Dima. , Hirsch, Edward A. , Pasechnik, Dmitrii V. |
| คำค้น | : | DRNTU::Science::Mathematics::Algebra. |
| หน่วยงาน | : | Nanyang Technological University, Singapore |
| ผู้ร่วมงาน | : | - |
| ปีพิมพ์ | : | 2545 |
| อ้างอิง | : | Grigoriev, D., Hirsch, E. A., & Pasechnik, D. V. (2002). Exponential Lower Bound for Static Semi-algebraic Proofs. Automata, Languages and Programming, 2380, 257-268. , http://hdl.handle.net/10220/18806 , http://dx.doi.org/10.1007/3-540-45465-9_23 |
| ที่มา | : | - |
| ความเชี่ยวชาญ | : | - |
| ความสัมพันธ์ | : | Automata, languages and programming |
| ขอบเขตของเนื้อหา | : | - |
| บทคัดย่อ/คำอธิบาย | : | Semi-algebraic proof systems were introduced in [1] as extensions of Lovász-Schrijver proof systems [2,3]. These systems are very strong; in particular, they have short proofs of Tseitin’s tautologies, the pigeonhole principle, the symmetric knapsack problem and the clique-coloring tautologies [1]. In this paper we study static versions of these systems. We prove an exponential lower bound on the length of proofs in one such system. The same bound for two tree-like (dynamic) systems follows. The proof is based on a lower bound on the “Boolean degree” of Positivstellensatz Calculus refutations of the symmetric knapsack problem. |
| บรรณานุกรม | : |
Grigoriev, Dima. , Hirsch, Edward A. , Pasechnik, Dmitrii V. . (2545). Exponential lower bound for static semi-algebraic proofs..
กรุงเทพมหานคร : Nanyang Technological University, Singapore. Grigoriev, Dima. , Hirsch, Edward A. , Pasechnik, Dmitrii V. . 2545. "Exponential lower bound for static semi-algebraic proofs.".
กรุงเทพมหานคร : Nanyang Technological University, Singapore. Grigoriev, Dima. , Hirsch, Edward A. , Pasechnik, Dmitrii V. . "Exponential lower bound for static semi-algebraic proofs.."
กรุงเทพมหานคร : Nanyang Technological University, Singapore, 2545. Print. Grigoriev, Dima. , Hirsch, Edward A. , Pasechnik, Dmitrii V. . Exponential lower bound for static semi-algebraic proofs.. กรุงเทพมหานคร : Nanyang Technological University, Singapore; 2545.
|
ridm@nrct.go.th ระบบคลังข้อมูลงานวิจัยไทย รายการโปรดที่คุณเลือกไว้
