Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Exact algorithm
open-in-new
<p>In <a href="/facts/Computer_science/lN3pEyPz">computer science</a> and <a href="/facts/Operations_research/H5yJkV5n">operations research</a>, exact algorithms are <a href="/facts/Algorithm/fnl5NmRt">algorithms</a> that always solve an optimization problem to optimality. </p><p>Unless <a href="/facts/P_%3D_NP/xoC7Ruda">P = NP</a>, an exact algorithm for an <a href="/facts/NP-hardness/mQeNPv4R"> NP-hard</a> optimization problem cannot run in worst-case <a href="/facts/Polynomial_time/77T62gmf">polynomial time</a>. There has been extensive research on finding exact algorithms whose running time is exponential with a low base. </p>