{"id":384,"date":"2015-11-20T23:30:25","date_gmt":"2015-11-21T04:30:25","guid":{"rendered":"http:\/\/aristotle2digital.blogwyrm.com\/?p=384"},"modified":"2021-11-25T20:46:37","modified_gmt":"2021-11-26T01:46:37","slug":"summing-up-is-np-hard-to-do","status":"publish","type":"post","link":"https:\/\/aristotle2digital.blogwyrm.com\/?p=384","title":{"rendered":"Summing Up is (NP) Hard to Do"},"content":{"rendered":"

One can\u2019t really be alive, work with computers, writing algorithms to solve hard problems, and be ignorant of the importance of a good algorithm.\u00a0 Most texts on scientific programming, which formed the bulk of what I read in my formative technical years, possess at least on cautionary tale about how slow a computation can be if the algorithm is bad.<\/p>\n

One classic tale I like, which is often trotted out with gusto, is the calculation of the Fibonacci numbers.\u00a0 As a reminder, the nth Fibonacci number is the sum of the two previous ones<\/p>\n

\\[\u00a0 F_n = F_{n-1} + F_{n-2} \\; . \\]<\/p>\n

So to compute $F_{100}$, one need to compute $F_{99}$ and $F_{98}$, each of which need the two below them.\u00a0 Computing naively causes a lot of repetition since one computes $F_{98}$ and $F_{97}$ to compute $F_{99}$ and $F_{97}$ and $F_{96}$ for $F_{98}$ and so on.\u00a0 Of course, a fast algorithm exists which essentially involves recording these values once computed, thus ensuring that they are computed only once in the recursion.<\/p>\n

While compelling, this cautionary tale is a bit of a cheat.\u00a0 Someone actually knows the best algorithm and it happens to be quite fast and, generally speaking, it isn\u2019t all that interesting to compute the Fibonacci numbers oneself, since they are immutable.<\/p>\n

Much more interesting are the situations that are dynamic.\u00a0 Finding the best route to visit an arbitrary list of cities is the stuff of legends with which the famous Traveling Salesman Problem<\/a> (TSP) wrestles.\u00a0 This problem is often listed as hard, or rather NP-Complete, a class of algorithms that belongs to the larger class of NP-Hard problems.<\/p>\n

Roughly speaking, NP problems (or which NP-Complete and NP-Hard belong) are computational problems that do not possess known algorithms that can find solutions in polynomial time.\u00a0 What that means is that as the input data set, usually thought of as consisting of $N$ entries, is increased (i.e. $N$ grows) the computing time required to find a solution grows much fasters than any polynomial in $N$.\u00a0 Usually the growth is exponential, although worse cases, such as combinatorial growth, also occur.\u00a0 This is in sharp contrast with the P class of computational problems<\/a> that do possess known algorithms that can find solutions in polynomial time.<\/p>\n

The curious thing about NP problems are that while they are not quickly solvable, they are quickly checkable.\u00a0 This phrasing means that while it takes a long time to find a solution for a large input data set, once the solution has been found it can be verified in a relative short period of time that scales as a polynomial in $N$.<\/p>\n

This distinction is hard to understand and this difficulty is compounded by the fact that the NP class has three qualifiers making for NP, NP-Complete, and NP-Hard as well as containing the P class.\u00a0 In addition, problems like the TSP are very specialized and complex making them very hard to relate to in general<\/p>\n

\"NP_hard\"<\/a><\/p>\n

Note: The reason NP-Hard lies partially outside the NP boundary is because some NP-Hard may not even be decidable. Undecidable problems possess no definitive answer to the computing question with which they are posed.\u00a0 That such problems exist inescapably follows from Turing\u2019s analysis of the halting problem.<\/p>\n

So I searched for a simplified problem that I could sink my teeth into.\u00a0 A problem that would be tractable enough to play with but still demonstrated the \u2018NP-ness\u2019 in a way that I could relate.\u00a0 After some trial-and-error, it seems that Subset Sum Problem (SSP) fits the bill.<\/p>\n

The SSP asks the following question.\u00a0 Given a sum $S$ and a set of integers $Q$ is there a proper subset of $Q$ that sums to $S$.\u00a0\u00a0 It is provable that the SSP is NP-Complete:\u00a0 a solution exists (i.e. the problem is decidable) ; it is hard to find a solution, especially when $Q$ has a lot of elements; and it is easy to check the solution once the answer is revealed.<\/p>\n

That the SSP is decidable is actually trivial to see.\u00a0 Given a subset $P \\in Q$ of integers, it is easy to sum them together and to test whether the result equals $S$.\u00a0 By playing with a simple configuration for $Q$, it was easy to demonstrate that it is hard to just find a subset that sums to the desired value and that is equal easy to check once an answer is proffered.<\/p>\n

Consider the following $3 \\times 4$ block of integers between 1-9, inclusive.<\/p>\n

\"3x4<\/a><\/p>\n

The sum of all of them is 53 and the smallest number in the set is 1, so it is also easy to answer no to the SSP when $S$ is outside this range.\u00a0 But what about the rest of the values?\u00a0 Can any value between 1 and 53 be represented?\u00a0 (It should be clear that 1 is represented trivially by one of the 1s in Q and that 53 is represented by the whole set).<\/p>\n

For a test, can we find a subset that sums to 19?\u00a0 That answer is obvious if one stares at the grid for a while.\u00a0 Since there is a 9 in the grid, all one needs to find is two numbers that sum to 10 in order to demonstrate that 19 is a valid subset sum.\u00a0 One such possibility is<\/p>\n

\"subset_sum_19\"<\/a><\/p>\n

How should we go about answering the general question?\u00a0 This is where the NP part comes in.\u00a0 In general, the best algorithms known are not polynomial in complexity.\u00a0 I won\u2019t try to prove this; I am simply stating the conclusion of the computer science community.\u00a0\u00a0 But being NP, it is easy to check that a proposed solution is valid in polynomial time.\u00a0 For example, it may not be obvious that 47 is contained as a subset sum within the grid but the following shows it to be true<\/p>\n

\"subset_sum_47\"<\/a><\/p>\n

Each of the blocks of different shades of red sum to 10 (i.e.: 6 + 4; 9 + 1; 8 + 2; 5 + 4 + 1) and the light orange block is a 7. Checking that solution is easier than finding it in the first place or in finding an alternative (note that one trivial change can be done in 3 cell to get a different set that subset sums to 47 \u2013 hint \u2013 look at the blocks that remained white).<\/p>\n

Now back to the general question as to whether any sum can be constructed.\u00a0 Consider the grid now colored so that the red subsets sum to 30 and the white portion of the grid consists of the numbers 1, 2, 3, 4, 5, and 8.<\/p>\n

\"all_sum\"<\/a><\/p>\n

Since the numbers 1, 2, 3, and 4 can sum to every number on the range 1-10, we already have that all numbers from 1 to 40 are subset sums.\u00a0 For example, 27 can be formed from the two pairs of tens (say 1 + 9 & 7 + 3) and from 3 + 4.\u00a0 Finally since 8 + 2 = 10 and 8 + 3 = 11, the remaining sums from 41 through 52 are also achievable. \u00a0Thus we have proved that all values between 1 and 53 are achievable.<\/p>\n

Note that the time it takes to confirm any of these values is much shorter than the time it would take an algorithm to find these solutions.\u00a0 That is what it means to be NP-Complete.<\/p>\n","protected":false},"excerpt":{"rendered":"

One can\u2019t really be alive, work with computers, writing algorithms to solve hard problems, and be ignorant of the importance of a good algorithm.\u00a0 Most texts on scientific programming, which… Read more ><\/a><\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-384","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"_links":{"self":[{"href":"https:\/\/aristotle2digital.blogwyrm.com\/index.php?rest_route=\/wp\/v2\/posts\/384","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/aristotle2digital.blogwyrm.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/aristotle2digital.blogwyrm.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/aristotle2digital.blogwyrm.com\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/aristotle2digital.blogwyrm.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=384"}],"version-history":[{"count":0,"href":"https:\/\/aristotle2digital.blogwyrm.com\/index.php?rest_route=\/wp\/v2\/posts\/384\/revisions"}],"wp:attachment":[{"href":"https:\/\/aristotle2digital.blogwyrm.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=384"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/aristotle2digital.blogwyrm.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=384"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/aristotle2digital.blogwyrm.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=384"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}