Combinatorial Algorithms and Real Algebraic Geometry

组合算法和实代数几何

• 批准号: 9402640
• 负责人: Richard Pollack
• 金额: $ 7.1万
• 依托单位: New York University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1994
• 资助国家: 美国
• 起止时间: 1994-08-15 至 1997-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9402640&HistoricalAwards=false
• 关键词: Combinatorial; Algorithms; Real; Algebraic; Geometry

9402640 Pollack This project is devoted to improving algorithms for the existential theory of the reals, the general decision problem for real closed fields and quantifier elimination over real closed fields. The goal is to be able to separate the complexity of these algorithms into a combinatorial part (the dependence on the number of input polynomials) and an algebraic part (the dependence on the degrees of these polynomials). The project should produce algorithms which are combinatorially optimal. One step in such algorithms is to compute a set of points which meet every cell determined by a family of polynomials. The project will extend this task, and will compute a set of points on a variety of real dimension k which meets every cell of a family of polynomials in such a way that the combinatorial complexity depends optimally on k. ***

9402640 Pollack 该项目致力于改进实数存在理论、实数闭域的一般决策问题以及实数闭域上的量词消除的算法。 目标是能够将这些算法的复杂性分为组合部分（依赖于输入多项式的数量）和代数部分（依赖于这些多项式的次数）。 该项目应该产生组合最优的算法。 此类算法的一个步骤是计算满足由多项式族确定的每个单元的一组点。 该项目将扩展此任务，并将计算各种实际维度 k 上的一组点，这些点满足多项式族的每个单元格，使得组合复杂度最佳地取决于 k。 ***