CMU 15-110: Principles of Computing
Tractability + NP-Completeness

---

Note: while the talk in class included more details on this topic, these notes will focus on what you need to know for the quiz and the final:

---

• subsetSum
  Given a list L of numbers, find a sublist M such that sum(M) is 0. For example, given this list:

  L = [42, 18, -27, -30, 4, -16, 5, 2]
  

  Find this sublist:

  M = [42,          -30, 4, -16      ]
  



• Brute Force
  How to solve subsetSum? About the best way we know so far is just to try every possible solution. This is known as using brute force, and it's awful. If L contains N values, then brute force requires checking 2^N sublists (so it is exponential). So if L contains just 40 values, then we have to check 2⁴⁰, or about 1 trillion sublists. If L contains 256 values, we'd need to check about as many sublists as there are atoms in the universe. Note that we can be very clever and do slightly better than brute force, but even so the best known solution is still exponential, which is intractable.


• Tractable
  A problem is tractable if it can be solved quickly enough that we can practically use that solution. Before this lecture, we have only seen tractable problems, including searching, sorting, all our homework and exam exercises, and so on.


• Intractable
  A problem is intractable if it can be solved, but unfortunately it may take too long to practically use that solution. Often, far too long, as in longer than the universe has existed. For example, using brute force to solve subsetSum works in theory but it is intractable.


• P
  We use P to denote problems that can be solved in Polynomial Time. For example, in O(N), or O(N²), or O(N³), and so on. Generally, we think of these as "fast" or at least "fast enough". So problems in P are tractable. For example, even though selectionSort at O(N²) is much slower than mergeSort at O(Nlogn), selectionSort is still in P so we say that selectionSort is tractable.


• NP
  We use NP to denote problems that can be solved in Non-deterministic Polynomial Time. This means that if we somehow were magically given a solution (by an oracle), that we could verify that the solution is correct quickly (in P). For example, while finding a solution M for a list L in subsetSum seems very hard, we can very easily and quickly verify that solution is in fact correct (just add the numbers in M and confirm the sum is 0). So subsetSum is in NP.


• NP-Complete
  SubsetSum is in fact NP-Complete. All the NP-Complete problems are in NP, and if you somehow manage to solve one of them quickly (in P), then you can use that solution to solve ALL of them quickly (in P). So, either ALL of them or NONE of them are in P. NP-Complete Problems include subsetSum, the Travelling Salesman Problem, Bin Packing, Scheduling, and many many others.


• Does P == NP?
  This is The Big Question! Is there a way to quickly (in P) solve the NP-Complete problems? As of today, we do not know. Maybe, maybe not. But we do know the consequences are huge, so it's worth knowing!
  
  If you constructively solve subsetSum quickly (in P), then...
  • P == NP
  • You can solve ALL NP-Complete problems quickly (in P)
  • Nearly everything in the world basically gets better (using optimal rather than approximate solutions to many important problems)
  • You are famous, and you win multiple $1M prizes
  • And... You can make vastly MORE money by selling solutions to NP-Complete problems!
  
  On the other hand, if you prove subsetSum cannot be solved quickly (not in P), then...
  • P != NP
  • You cannot solve ANY NP-Complete problems quickly (in P)
  • Nothing in the world practically gets better (we're still left using approximate solutions to many important problems)
  • You STILL are famous, and you STILL win multiple $1M prizes
  
  Aside: there is a third option: you prove P == NP, but non-constructively, so we know it's true but we don't have an actual algorithm we can use to quickly solve NP-Complete problems. In that case, you win those $1M prizes and fame and glory, and then no doubt you set off a mad chase after a constructive proof, since that is what we need to actually solve those important problems quickly!
  
  Aside to the aside: and there is alas a fourth option: that this is itself unprovable. It may be impossible to prove either that P == NP or that P != NP. So we may never know.


• The Bottom Line
  
  • We do not know if P == NP
  • So, for example: we do not know if subsetSum is tractable
  • And: it's really important that we find out!!!!!

---