User:Realazthat/Projects wishlist/NP/Reduction library: Difference between revisions
Content added Content deleted
(Created page with ' Make an NP-complete reduction library, which will be capable of reducing NP-complete problems to each-other. '''Features:''' * Computation of exact complexity ** By annotation …') |
No edit summary |
||
| (3 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
Make an NP-complete reduction library, which will be capable of reducing NP-complete problems to each-other. |
Make an NP-complete reduction library, which will be capable of reducing NP-complete problems to each-other. |
||
| Line 6: | Line 5: | ||
** By annotation of functions with their complexity |
** By annotation of functions with their complexity |
||
** Stacking of functions annotations |
** Stacking of functions annotations |
||
* SAT to DHC |
|||
** http://www.ecst.csuchico.edu/~amk/foo/csci650/notes/ch11/NP4.html |
|||
** http://cs482.elliottback.com/lecture-25-hamiltonian-cycle-problem/ |
|||
** http://www.compgeom.com/~piyush/teach/AA05/slides/lecture8.ppt |
|||
** www.cs.uiuc.edu/class/sp08/cs473/Lectures/lec18.pdf |
|||
* DHC to UHC |
|||
** http://www.ecst.csuchico.edu/~amk/foo/csci356/notes/ch11/ch11.html |
|||
* SAT to 3SAT |
|||
** www.cs.uiuc.edu/class/sp08/cs473/Lectures/lec18.pdf |
|||
Latest revision as of 23:02, 2 December 2010
Make an NP-complete reduction library, which will be capable of reducing NP-complete problems to each-other.
Features:
- Computation of exact complexity
- By annotation of functions with their complexity
- Stacking of functions annotations
- SAT to DHC
- http://www.ecst.csuchico.edu/~amk/foo/csci650/notes/ch11/NP4.html
- http://cs482.elliottback.com/lecture-25-hamiltonian-cycle-problem/
- http://www.compgeom.com/~piyush/teach/AA05/slides/lecture8.ppt
- www.cs.uiuc.edu/class/sp08/cs473/Lectures/lec18.pdf
- DHC to UHC
- SAT to 3SAT
- www.cs.uiuc.edu/class/sp08/cs473/Lectures/lec18.pdf