Previous
Next

Math Monday: TV Lawyers Solve NP-Complete Problem (part 1)

October 17, 2011, 7:30 am

For the next couple of weeks, Math Monday here at the blog will feature a guest blogger. Ed Aboufadel is Professor of Mathematics and chair of the Mathematics Department at Grand Valley State University, where I work. He’ll be writing a two-part series on a neat appearance of an NP-complete problem on network TV, adding yet another data point that mathematics is indeed everywhere. Thanks in advance, Ed!

On the new USA-network TV series Suits [1], Harvey Specter is a senior partner at the law firm of Pearson Hardman, and Mike Ross is his new associate. Mike never went to law school, but he combines a photographic, elephantine memory with near-genius intelligence to fake it well. Harvey is in on the deception, but none of the other partners know. During the eighth episode of the first season of Suits (broadcast August 11, 2011), Harvey and Mike, working with Louis Litt, a socially-challenged junior partner, solved an NP-complete problem in a short amount of time in order to rescue over $150 million for a client. Were they just lucky, smarter than the rest of us, or did they do something practically impossible?

In the story, Lucille Jackson, a client of Pearson Hardman, needed help to deal with an investment firm led by Tony Maslow. Lucille had trusted the firm with over $150 million that belonged to a non-profit organization similar to Habitat for Humanity. The investment firm claimed to have lost the money due to poor investments, and due to the malfeasance of one of Tony’s partners who conveniently dies early in the episode. Eventually, Harvey, Mike, and Louis figure out that Maslow had hidden the money overseas, and with the help of biology student and hacker extraordinaire Lola Jensen, they pull together the following information:

  • The exact amount that was embezzled was $152,375,242.18.
  • On one day, all of the money was wired to one or more banks in Liechtenstein, but they don’t know which banks were involved.
  • There are sixteen banks in Liechtenstein.
  • For the day the money was transferred, the lawyers have a list of every deposit made to every account for every bank in Liechtenstein (but no information about where the deposits came from).
  • The deposits at eleven of the sixteen banks can be ignored for various legal reasons.

In order to confront Tony with proof of the embezzlement, Harvey, Mike, and Louis determine that they need to identify a collection of deposits to the five banks that add up to exactly $152,375,242.18. Louis remarks that this is “simple mathematics”. It certainly is a simple problem to state, but it is not clear if it is a simple problem to solve.

The problem they needed to solve is called subset-sum: given a set of integers \( S \) and a target \(k\), is there a subset of \(S\) whose elements add up exactly to \(k\)? (Since we are dealing with money, multiply everything by 100 so that we have integers.) Stated this way, subset-sum is a yes-no decision problem, but asking for the elements in the subset is an equivalent problem [2].

Subset-sum is related to other decision problems such as the traveling salesman problem and the knapsack problem, and games like FreeCell. These problems are known as NP-complete problems which arise in theoretical computer science. “Brute force” solutions of these problems involve generating a large, finite collection of all possible solutions, and then checking each element of the collection until an actual solution is found. Checking a potential solution is quick (what computer scientists refer to as “polynomial time”) but generating the complete collection of solutions can take a long time. For example, in the subset-sum problem where there are 25 elements in \(S\), then \(S\) has \(2^{25}\), or over 33 million, subsets. It would take a long time to write down or generate all of these subsets, but not very long to determine if the elements of a specific subset summed to a target \(k\).

Generally, the time needed to solve an NP-complete problem grows based on the size of the inputs into the problem, due to the time needed to generate all possible solutions. In the case of subset-sum, if \(S\) has \(n\) elements, then there are \(2^n\) subsets to generate. Now a solver might get lucky and generates the subset that adds up to \(k\) early in the solution process. But theoretically, it may be necessary to inspect all \(2^n\) subsets before finding the subset that adds up to the target or to determine that the subset does not exist.

All NP-complete problems can be solved using this “brute force” approach. At the same time, solution methods have been developed for NP-complete problems that are fast most of the time (which are appreciated by industries such as airlines and telecommunications), but they are not perfect methods. The algorithms might be designed to solve the problem quickly for a typical instance of the problem, but these methods are vulnerable to rare instances of requiring the inspection of all possible solutions. It also the case that there are fast methods that find a nearly- optimal solution rather than an optimal one, which is often sufficient in real applications. (With subset-sum, an example would be to find a subset that sums up to within 1% of the target \(k\).)

Another fascinating fact about NP-complete problems is that a solution method to one of the problems can, in theory, be modified to solve any other NP-complete problem. This theoretical result comes from reducing any NP-complete problem to a Boolean logic problem known as satisfiability.

Returning to Harvey, Mike, and Louis, although no details are provided on the show, they solve their subset-sum problem, finding a set of seven deposits from the five banks that add up to exactly $152,375,242.18. The lawyers didn’t have a lot of time to solve the problem. In the story, when they realize the “simple” mathematics problem that they needed to solve, it was nighttime on what was a warm, sunny day in New York City. On the following day, clean, showered, and refreshed, they have the details about the seven deposits ready for a meeting with Tony and his lawyer. After confronted with the deposits, Tony returns all of the money to the house-building charity, and once again, mathematics saved the day!

So, were they lucky? Did they happen upon a subset of the set of deposits in a short period of time? Did they have a solution method handy that solved this particular instance quickly? Perhaps near-genius Mike had an insight after reading all the deposits into his photographic memory. In Part II, we will explore the likelihood that they could solve the problem given the time they had.

References for Part I:
[1] http://en.wikipedia.org/wiki/Suits_%28TV_series%29
[2] Cormen, T. et al, Introduction to Algorithms, 2nd edition, the MIT Press, 2001.

Image: http://www.flickr.com/photos/amagill/

This entry was posted in Math, Weekly features and tagged , , , , , . Bookmark the permalink.