NP Completeness: Difference between revisions

From NovaOrdis Knowledge Base
Jump to navigation Jump to search
Line 25: Line 25:
<span id='NP-complete_Problems'></span>Almost all the algorithms mentioned so far have been '''polynomial-time algorithms''', which is to say that on an input of size n, their worst running time is O(n<sup>k</sup>) for some constant k. Generally, we think of a problem that is solvable by a polynomial-time algorithm as '''tractable''' or '''easy'''. A problem that requires super-polynomial time is designated '''intractable''' or '''hard'''. There are also problems whose status is unknown: no polynomial-time algorithm has been yet discovered for them, nor has anyone yet been able to prove that no polynomial-time algorithm can exist for any of them. This class of problems is called [[NP Completeness#Overview|NP-complete problems]]. The set of NP-complete problems has the property that if an efficient algorithm exists for any one of them, then efficient algorithms exist for all of them. There are methods to show that a problem is NP-complete, and if that is the case, an '''approximation algorithm''' instead of a polynomial-time algorithm, can be developed form it.
<span id='NP-complete_Problems'></span>Almost all the algorithms mentioned so far have been '''polynomial-time algorithms''', which is to say that on an input of size n, their worst running time is O(n<sup>k</sup>) for some constant k. Generally, we think of a problem that is solvable by a polynomial-time algorithm as '''tractable''' or '''easy'''. A problem that requires super-polynomial time is designated '''intractable''' or '''hard'''. There are also problems whose status is unknown: no polynomial-time algorithm has been yet discovered for them, nor has anyone yet been able to prove that no polynomial-time algorithm can exist for any of them. This class of problems is called [[NP Completeness#Overview|NP-complete problems]]. The set of NP-complete problems has the property that if an efficient algorithm exists for any one of them, then efficient algorithms exist for all of them. There are methods to show that a problem is NP-complete, and if that is the case, an '''approximation algorithm''' instead of a polynomial-time algorithm, can be developed form it.


<font color=darkkhaki>TODO</font>
<font color=darkkhaki>TODO.</font>


=Subjects=
=Subjects=
* [[Traveling Salesman Problem]]
* [[Traveling Salesman Problem]]
* <font color=darkkhaki>Local Search</font>
* <font color=darkkhaki>Local Search</font>

Revision as of 00:00, 30 November 2021

External

Internal

Overview

Almost all the algorithms mentioned so far have been polynomial-time algorithms, which is to say that on an input of size n, their worst running time is O(nk) for some constant k. Generally, we think of a problem that is solvable by a polynomial-time algorithm as tractable or easy. A problem that requires super-polynomial time is designated intractable or hard. There are also problems whose status is unknown: no polynomial-time algorithm has been yet discovered for them, nor has anyone yet been able to prove that no polynomial-time algorithm can exist for any of them. This class of problems is called NP-complete problems. The set of NP-complete problems has the property that if an efficient algorithm exists for any one of them, then efficient algorithms exist for all of them. There are methods to show that a problem is NP-complete, and if that is the case, an approximation algorithm instead of a polynomial-time algorithm, can be developed form it.

TODO.

Subjects