NP Completeness: Difference between revisions
Jump to navigation
Jump to search
| (13 intermediate revisions by the same user not shown) | |||
| Line 15: | Line 15: | ||
* https://www.coursera.org/learn/algorithms-npcomplete/lecture/qtdIZ/knapsack-via-dynamic-programming-revisited | * https://www.coursera.org/learn/algorithms-npcomplete/lecture/qtdIZ/knapsack-via-dynamic-programming-revisited | ||
* https://www.coursera.org/learn/algorithms-npcomplete/lecture/ApF82/ananysis-of-dynamic-programming-heuristic | * https://www.coursera.org/learn/algorithms-npcomplete/lecture/ApF82/ananysis-of-dynamic-programming-heuristic | ||
* https://www.coursera.org/learn/algorithms-npcomplete/lecture/8Pe2F/stable-matching-optional | |||
=Internal= | =Internal= | ||
| Line 21: | Line 22: | ||
<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]] | ||
* [[Local Search]] | |||
** [[The Maximum Cut Problem]] | |||
** [[The 2SAT Problem]] | |||
Latest revision as of 04:05, 30 November 2021
External
- https://www.coursera.org/learn/algorithms-npcomplete/lecture/8HT5O/polynomial-time-solvable-problems
- https://www.coursera.org/learn/algorithms-npcomplete/lecture/o1CGE/reductions-and-completeness
- https://www.coursera.org/learn/algorithms-npcomplete/lecture/vZ9Bc/definition-and-interpretation-of-np-completeness-i
- https://www.coursera.org/learn/algorithms-npcomplete/lecture/3JqiX/definition-and-interpretation-of-np-completeness-ii
- https://www.coursera.org/learn/algorithms-npcomplete/lecture/VZY2Z/the-p-vs-np-question
- https://www.coursera.org/learn/algorithms-npcomplete/lecture/jugfP/algorithmic-approaches-to-np-complete-problems
- https://www.coursera.org/learn/algorithms-npcomplete/lecture/fxmkY/the-vertex-cover-problem
- https://www.coursera.org/learn/algorithms-npcomplete/lecture/2or0q/smarter-search-for-vertex-cover-i
- https://www.coursera.org/learn/algorithms-npcomplete/lecture/lPiFO/smarter-search-for-vertex-cover-ii
- https://www.coursera.org/learn/algorithms-npcomplete/lecture/EAWJa/a-greedy-knapsack-heuristic
- https://www.coursera.org/learn/algorithms-npcomplete/lecture/OR1PW/analysis-of-a-greedy-knapsack-heuristic-i
- https://www.coursera.org/learn/algorithms-npcomplete/lecture/kGddv/analysis-of-a-greedy-knapsack-heuristic-ii
- https://www.coursera.org/learn/algorithms-npcomplete/lecture/gXaGS/a-dynamic-programming-heuristic-for-knapsack
- https://www.coursera.org/learn/algorithms-npcomplete/lecture/qtdIZ/knapsack-via-dynamic-programming-revisited
- https://www.coursera.org/learn/algorithms-npcomplete/lecture/ApF82/ananysis-of-dynamic-programming-heuristic
- https://www.coursera.org/learn/algorithms-npcomplete/lecture/8Pe2F/stable-matching-optional
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.