User:Realazthat/Projects wishlist/NP/Reduction library

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
  • 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