[prev] 92 [next]

Example: Subset Sum (cont)

Subset Sum is typical member of the class of NP-complete problems
  • intractable … only algorithms with exponential performance are known
    • increase input size by 1, double the execution time
    • increase input size by 100, it takes 2100 = 1,267,650,600,228,229,401,496,703,205,376 times as long to execute
  • but if you can find a polynomial algorithm for Subset Sum, then any other NP-complete problem becomes P …