کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4609029 | 1338402 | 2009 | 13 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Some lower bounds for the complexity of the linear programming feasibility problem over the reals
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
آنالیز ریاضی
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: Some lower bounds for the complexity of the linear programming feasibility problem over the reals Some lower bounds for the complexity of the linear programming feasibility problem over the reals](/preview/png/4609029.png)
چکیده انگلیسی
We analyze the arithmetic complexity of the linear programming feasibility problem over the reals. For the case of polyhedra defined by 2n2n half-spaces in Rn we prove that the set I(2n,n)I(2n,n), of parameters describing nonempty polyhedra, has an exponential number of limiting hypersurfaces . From this geometric result we obtain, as a corollary, the existence of a constant c>1c>1 such that, if dense or sparse representation is used to code polynomials, the length of any quantifier-free formula expressing the set I(2n,n)I(2n,n) is bounded from below by Ω(cn)Ω(cn). Other related complexity results are stated; in particular, a lower bound for algebraic computation trees based on the notion of limiting hypersurface is presented.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Complexity - Volume 25, Issue 1, February 2009, Pages 25–37
Journal: Journal of Complexity - Volume 25, Issue 1, February 2009, Pages 25–37
نویسندگان
Rafael Grimson, Bart Kuijpers,