Exploring the Frontiers of Feasible Computation

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

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.