Wednesday, September 16, 2009

Wednesday Math, Vol. 88: 3-SAT

Last week, I talked about subset sum, one of the problems that is NP-Complete. NP-Complete is a set of problems, many of them easy to explain but all of them hard to solve in a general way. Any particular example of a problem is called an instance, and we can come up with a nice method that will take care of some instances in a very tidy way, but with any method for an NP-Complete problem, there will be instances that are very thorny.

The particular problem I talked about last week was subset sum, and this week the topic is 3 SAT. The idea can be put forward in many ways, but all the different settings are really different ways to look at the same problem.

Consider that you are a deejay at a gigantic dance club with seven different dance floors, and you have seven different turntables, each one broadcasting a song to one of the dance floors. Everyone in the club has sent you a card with three requests out of a possible fourteen songs on seven records, each record with an A side and a B side. Your job is to make everybody happy, play seven songs on seven dance floors so that everyone who filled out a card has at least one song playing somewhere that was one of their requests. You have 2^7 = 128 different choices for the songs playing on the seven dance floors, and it is possible that given the particular cards sent in, it will be impossible to satisfy everyone, that there will be at least one customer who refuses to dance. We will say you solved the problem if you can get everyone to dance, or if it is impossible, for you to state correctly that it is impossible.

I chose seven dance floors at random. The thing about any instance of this problem that isn't random is that everyone sent in a card with three choices, which is why it is called 3-SAT, short for three satisfiable. It could be many, many more dance floors with a record for each one, but the problem is officially solved when you put the records on and everyone dances, or you claim that it's impossible to get everyone to dance and you are correct in your claim.

I've tried to turn some of the classic NP-Complete problems into games that could be turned into phone app games. I still believe it's possible, but I haven't found the game that really clicks yet. My feeling that there might be that one that clicks comes from the fact that both Tetris and Minesweeper have been proven to be part of NP-Complete.

The search continues.

No comments: