3SAT 2SAT MESAT YOUSAT

"Traveling Salesman has driven men to drink"
--Moshe Kam

NP Complete and I go way back. Way, way back. Back before I knew that NP stood for "nondeterministic polynomial" and not "non-polynomial." This is how it usually goes:

First, I get some inspiration. Something someone else has probably tried before. Then I try it out, and it works. Yay! I start dreaming about what I'm going to do with the prize money for solving it while I set out to test my solution and then prove that it is polynomial. Then some little snag comes up. Some piece of the puzzle is either exponential, or wrong, and fixing requires adding an exponential algorithm. But I still think I've done it, so I spend the next few days or weeks trying to fix the problem. Every time I solve the exponential problem, some piece of that solution has its own, tiny exponential problem, and then that one has its own exponential problem, and eventually the problem I'm trying to tackle looks a lot like that thing in set theory where if you want to add a bunch of sets together you have to subtract the unions, but then you have to subtract the union-intersection from the unions, but you have to subtract the union-intersection-unions....and you have arrived at a problem that is exponential.

This time, it happened in roughly the same way. Except it started, like, monday, and its already thursday. Its like a drug. I can't pay attention in meetings because my mind is going over whichever little exponential snag is standing between me and one million dollars. And daydreaming about publishing a paper and using the letters "xkcd" for an example. This time, though, I came up against the set-union problem and backed up, and forced myself to completely rethink most of my solution.

In other words, I'm still in the rabbit hole. By not doing any work and using the whiteboard at my office, I've managed to, again, arrive at a solution that I think is polynomial but this time without using up all the paper in my apartment.

This time, though, I have little hope left for actually proving my solution. A week without adequate sleep, plus my caffeine overdose from last night is taking its toll, and I don't know how to prove my solution anymore.

I managed to establish this relationship between groups of expressions in 3SAT. That relationship was what was completely screwing me over all week but I managed to use it as an opportunity to prune the search space, allowing you to solve subproblems with fewer variables. I remember pruning having something to do with better run times, but all I really have is some vauge memory of my algorithms teacher writing something on the whiteboard.

So I'm going to keep going with this one, and if this last attempt fails I will give up. Until the next time. I'm not sure there will be a next time though; I can't imagine me ever getting closer than this. I mean, I made a hypercube out of two boxes. I can actually see the problem. It is likely that reason I always fail to solve the problem is that P!=NP and the solution I'm looking for doesn't exist. I have no clue how to prove that. I don't even understand the proof for why comparison sorting requires logarithmic time. One of the guys on my team here told me to use proof by contradiction...i.e. prove that it requires exponential time by assuming that it doesn't and failing to come up with an algorithm.

Man, what a rush. I think I stayed up all night tuesday because I was worried someone might solve it before I could.