Previous Article about the flipped MATLAB class Next Better examples through peer instruction

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

October 24, 2011, 7:30 am

This is the second installment of a two-part article from guest blogger Ed Aboufadel. Thanks again, Ed, for contributing.

In Part I, we learned of an instance of the NP-complete problem subset-sum [1] that was solved by three lawyers on an episode of the USA Network show Suits [2]. The problem was to go through a set of deposits made to five banks in Liechtenstein and find a subset of deposits, where the total of the deposits was $152,375,242.18. Described as “simple mathematics” by one of the lawyers, the team solved the problem in a relatively short length of time. They couldn’t use a quick approximation algorithm for subset-sum, since they needed the sum to be exactly equal to their target amount. So, were they just lucky, smarter than the rest of us, or did they do something practically impossible? Consider the following “back of the envelope” calculations. First, how much time did they have to solve the problem? In the story, when they realized the “simple” mathematics problem that they needed to solve, it was nighttime on what was a warm, sunny day in New York City. By the following day, they were ready for their meeting with the bad guy, having in hand a document listing a set of seven deposits that totaled exactly$152,375,242.18. They were also groomed, showered, and refreshed. If the episode occurred in September (still warm, but longer nights to solve math problems), then sunset is about 7:00 pm at the autumnal or fall equinox in New York City [3]. So, when the three lawyers met, it was 8:00pm at the earliest. If the meeting was in the afternoon the next day, we can conclude that they had 16 hours or so to solve the problem.

How many deposits did they have to sift through? According to a survey done by the United States Federal Deposit Insurance Corporation (FDIC) in 2008, the 683 United States banks that responded to the survey had a combined total of about 200 million accounts, or about 300 thousand accounts per bank [4]. A similar survey of banks in Germany in 2003 indicated only 42 thousand accounts per bank in that country [5]. Since Liechtenstein’s banks are known for their secrecy (much like Gringotts Bank in the Harry Potter books), they probably have even fewer accounts per bank than nearby Germany, so let’s assume that the average bank in Liechtenstein has 20 thousand accounts.

On a given day, how many of those accounts would have a deposit posted? Again, these are not your typical checking accounts, so a reasonable guess is that only 0.1% of the accounts have deposits per business day or 200 deposits per bank. Since there are five banks, our three protagonist lawyers were probably looking at about 1000 deposits. Figuring the bad guy would use all five banks, and he would not be interested in the hassle of too many accounts, it would have been reasonable to assume that he completed at least five deposits that day. We know now that the correct answer involved seven deposits, so let’s suppose that the lawyers inspected sets of five, six, or seven deposits. For a set S of size 1000, the number of subsets of size between five, six, or seven is about $$2 \times 10^{17}$$. That is a lot of subset sums to check.

Since it would have been reasonable to look for at least one deposit at each bank, there are actually fewer sums to consider, but we would still have an NP-complete problem. Starting with five sums, one from each bank, there would have been $$200^5$$ ways to choose deposits, which is about 320 billion, but none of these sums would have been what the lawyers were looking for.

So, after calculating and rejecting the 320 billion sums, the next step might have been to consider if there were two deposits at one of the banks. One way to have done this: subtract each of the 320 billion sums from \$152,375,242.18, removing those which are negative, and then checking if any of the remaining 995 deposits match up with the differences that were calculated. Taking a wild guess that 10% of the 320 billion were less than the target, the lawyers would still have been faced with 32 billion subtractions to calculate. Once those subtractions were done, comparing the results with the 995 deposits would have been easy and quick, especially for Mike the associate and his astounding memory. Of course, none of the 32 billion subtractions would have matched up with the 995 deposits. So, Harvey, Mike, and Louis would have taken their 32 billion results, added in a seventh deposit, and found the evidence they need to confront Tony. This part of the solution led to success.

Could all of this have been done is 16 hours? The lawyers would have needed a fast computer and ready-to-go computer code to generate and check possibilities. Just to check the 320 billion combinations of five deposits, they would have had to generate and examine 20 billion combinations per hour. In comparison, what is considered to be the current record for computing decimal places of π – done on a home computer – is 2.7 trillion digits in 131 days, or a rate close to one billion digits per hour [6].

What to make of all of this? Perhaps the lawyers had access to a supercomputer (or a room full of laptops) and a brilliant computer programmer. They may have developed a clever method to solve the problem that this author is not aware of. It is possible that once they got immersed in the problem, they realized it wasn’t so simple, said, “we need a little luck”, and since seven is a lucky number, started investigating sums of seven deposits. Then they were fortunate to find the solution quickly. Or maybe the writers of Suits thought a simply-stated mathematical problem should have a quick solution. Regardless, it is exciting to be watching USA Network and finding the opportunity to think about higher mathematics.

References for Part II:
[1] Cormen, T. et al, Introduction to Algorithms, 2nd edition, the MIT Press, 2001.
[2] http://en.wikipedia.org/wiki/Suits_%28TV_series%29
[3] http://www.timeanddate.com/worldclock/astronomy.html?n=179
[4] http://www.fdic.gov/unbankedsurveys/2008survey/index.html
[5] Hagendorff, J. et al, “Bank deregulation and acquisition activity: the cases of the US, Italy and Germany”, Journal of Financial Regulation and Compliance, Vol. 15 No. 2, 2007, pp. 199- 209, DOI 10.1108/13581980710744084
[6] http://bellard.org/pi/pi2700e9/announce.html

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

• The Chronicle of Higher Education
• 1255 Twenty-Third St., N.W.
• Washington, D.C. 20037