Exploring the Frontiers of Feasible Computation
This 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.
Return to Richard Brent's homepage