NP Completeness and Logical Satisfiability

• Introduction to kSAT and colorability
• kSAT Exercise
• Lecture on NP-completeness, computational complexity, and phase transitions
• Python:
  • Hints file for kSAT
  • Graphics software for animating kSAT
  • kSAT answer and demo

References

Links

• Course Web Page
• Book Web Page

Last modified: August 24, 2006

Statistical Mechanics: Entropy, Order Parameters, and Complexity, now available at Oxford University Press (USA, Europe).