Intractable Problems — Part One: Set Problems

My professor and advisor Dr. Alice McRae provided a list of intractable problems for us to ponder in our genetic algorithms class, and I thought I would expand on some of them here for reference. All of these problems are intractable, which means that they are very, very difficult to solve precisely with a computer.

Most of the problems on this list are what is known as NP-Complete problems. If the complexity classes P and NP are not equal (as is widely believed by many researchers, but not proven), then NP-Complete problems cannot be solved by a computer in a reasonable time frame. In theory, with an infinite amount of time we could produce answers to these problems but time and computing power is finite, no matter how many technological advances we make.

We have seen some of these difficult problems before in previous posts: Genetic Algorithms for Ramsey Theory and The Travelling Santa Problem, as well as Introduction to Genetic Algorithms all have good examples of these types of problems.

I will be presenting these problems in multiple parts, with my comments and references on each one.

Part One — Set Problems

Maximum 3-Dimensional Matching — given a set S of ordered triples of the form (x,y,z), find the largest possible subset of the triples, such that no two elements in the triple share the same x, y, or z coordinate.

Here is a small example: Consider the set \{(1,4,5),(3,4,9),(6,7,8),(1,2,5)\}. We need to find the largest subset of these we can, and the x,y,z values cannot be repeated. In this example, the set \{(3,4,9),(6,7,8),(1,2,5)\} would be a solution. It contains 3 triples and none of the numbers are repeated. As you can imagine, once the sets gets larger, this problem becomes much more difficult.

In layman’s terms, consider a group of boys, girls, and pets. We want to make happy “triplets” of girls, boys, and pets, but no girl, boy or pet can be in more than one group. What is the best way to match these people and pets up so that we have the largest number of groups?

Class: 3-Dimensional Matching (finding any subset that satisfies the conditions) is NP-Complete. The optimization problem (finding the largest subset) is NP-Hard. [1]

References: 

More NP-Completeness Results (pdf) lecture notes from CMU, good explanation of 3DM as well as some other problems, proof of the class of 3DM.

NP-Complete Problems (pdf, pg 267)

============================

Subset Sum/Subset Product — given a set S of integers and a goal sum/product P, find a subset of S that sums/multiplies as close as possible to the goal of P.

This one doesn’t sound as hard, but at larger quantities, this can become very difficult.

Example: Consider the set S = \{ n |1\leq n \leq 100 \} and a goal sum G = 531. Now we need to find a set of numbers between 1 and 100 that we can add together to get 531.

A practical application of this: Say you’re a kid and your parents gave you $10 of allowance for the week. Naturally, you want to get as much good out of that $10 as you can. What is the best combination of things you can buy to add up to as close to $10 all together?

Class: Subset sum and subset product are NP-Complete. Proof can be found at [2]

References:

Subset Sum NP-Completeness (pdf) Scroll down a bit to see the proof that subset sum is in NP-Complete

Dynamic Programming Subset Sum — A description of a dynamic programming technique for this problem

SubsetSum@Home — A distributed crowdsourced BOINC-type initiative to solve subset sum problems

An Improved Low-Desnity Subset Sum Algorithm — a paper concerning algorithms to solve this problem

============================

Minimum Set Covering — given a set S and a collection C of subsets over S, find the fewest number of subsets of C such that all elements of S are represented.

Okay so lets break this down. We have a set S, lets say for example S=\{1,2,3,4,5\}. Now we have a collection C of subsets over S. For our example, C = \{\{1\},\{2,5\},\{3,4\},\{2,3,4\},\{5\}\}.  In this case, the smallest collection we can make that includes all the elements in S is \{\{1\},\{2,3,4\},\{5\}\} which contains 3 elements.

Practical example: You’re a kid again, and looking at a group of video games that are on sale. They are all in combo packs, however. How can you get all the games you want and spend as little money as possible? In other words, what is the smallest amount of combo packs you need to buy in order to get all of the games you want?

Class: the decision problem (does this set contain all the elements we’re looking for?) is NP-Complete. The optimization problem (is this set the smallest set we can make?) is NP-Hard. See [3].

References:

A Probabilistic Heuristic for a Computationally Difficult Set Covering Problem – (pdf) Journal article on this topic detailing a heuristic for finding set coverings

A Genetic Algorithm for the Set Covering Problem – (pdf) Journal article about a genetic programming approach to set cover

A Greedy Heuristic for the Set-Covering Problem – (pdf) Yet another approach

Set Cover Problem — Wikipedia

An Example: Set Cover – (pdf) Scroll down to see a proof of set cover in NP-Complete

============================

These are only a few intractable set problems, but there are many more variations of these out there. Stay tuned for the next segment in this series, problems about Data Storage (Bin Packing and Knapsack).

Advertisements

2 comments on “Intractable Problems — Part One: Set Problems

  1. […] post continues my series on intractable problems. In this installment, I will talk about problems relating to Data Storage. As a refresher, remember […]

  2. […] also be applied to many logistical and optimization problems (see my posts on intractable problems here and here). For many of the NP problems, finding an “easy” method to solve one can be […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s