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。 ***