Oct 23, 2017
Evidence of an exponential speed-up in the solution of hard optimization problems
Fabio Lorenzo Traversa, Massimiliano Di Ventra, Pietro Cicotti, Forrest Sheldon,
Optimization problems pervade essentially every scientific discipline and industry. Many such problems require finding a solution that maximizes the number of constraints satisfied. Often, these problems are particularly difficult to solve because they belong to the NP-hard class, namely algorithms that always find a solution in polynomial time are not known. Over the past decades, research has focused on developing heuristic approaches that attempt to find an approximation to the solution. However, despite numerous research efforts, in many cases even approximations to the optimal solution are hard to find, as the computational time for further refining a candidate solution grows exponentially with input size. …
[searchandfilter fields=”post_tag”]