Exploring the Frontiers of Feasible Computation

探索可行计算的前沿

• 批准号: FF0455774
• 负责人: Prof Richard Brent
• 金额: $ 107.6万
• 依托单位: The Australian National University
• 依托单位国家: 澳大利亚
• 项目类别: Federation Fellowships
• 财政年份: 2005
• 资助国家: 澳大利亚
• 起止时间: 2005-03-14 至 2010-03-13
• 项目状态: 已结题
• 来源: https://dataportal.arc.gov.au/RGS/Web/Grants/FF0455774
• 关键词: Exploring; Frontiers; Feasible; Computation

The project aims to delineate the boundary between feasible and infeasible computational problems. A problem is considered feasible if there is an algorithm to solve it in worst-case time bounded by a polynomial in the input size. This is probably impossible for the important class of NP-complete problems. However, typical examples of NP-complete problems can often be solved in polynomial time, because worst-case problems are rare. The project is relevant to public-key cryptography, where breaking an encryption scheme should be infeasible, and to many real-life situations where NP-complete problems need to be solved, either exactly or approximately.

该项目旨在划定可行和不可行的计算问题之间的边界。一个问题被认为是可行的，如果有一个算法，以解决它在最坏情况下的时间限制在一个多项式的输入大小。 这对于重要的NP完全问题是不可能的。然而，NP完全问题的典型例子通常可以在多项式时间内解决，因为最坏情况的问题很少。该项目与公钥密码学有关，在公钥密码学中，破解加密方案应该是不可行的，并且与许多需要精确或近似解决NP完全问题的现实生活情况有关。