Depth-First Insanity (DFI)

I've been going since maybe Friday night without finding an hole in my solution. I've run through the algorithm on paper, and by paper I mean a series of cardboard cubes scattered around my apartment. I took some pictures; I'll try to upload them here sometime. Actually they are not just cardboard. I don't know if you know this, but projecting a hypercube into 3 dimensions requires twice as many physical cubes every time you add a dimensions. Suffice to say I need a lot of cubes.

The first cube was constructed by taping a box of jello mix onto a box of pudding and slapping some paper on time. Then I needed a cube in four dimensions, which means I needed two cubes: one for positive w and one for negative w (the first 3 dimensions are x,y and z). If this doesn't make sense to you, stop reading now. So anyway I had ordered a video converter so that the next time Firefly girl and I watch Castle I can go to her place and play the videos from my laptop. Anyway, so I spent like an hour or two cutting up this box at work. Now I had a cube for w and a cube for !w. Well, then I added the A dimensions, so I had to go up to four cubes. But then I wanted to add the B dimensions, but I had already put stickers all over my x-y-z-w-a cubes in case anyone wanted to come over and check out my hypercube (no one does) so then I needed 8 more cubes. And after that I realized that my data structure was growing exponentially, and I needed to start analyzing various projections of the hypercube into 3 dimensions. Like, for a hypercube with dimensions x,y,z,w,a,b, I wanted to look at a cubic projection of x,y,z, and y,z,w, and z,w,a, and w,a,b, etc.

So my quest to solve the hardest problem in computer science temporarily became a quest to find cube-shaped objects. I cut up a box of toothpaste and one or two other objects lying around my place and then left at like 2 am friday night to go to 7-11 in search of anything shaped like a cube. I tried to avoid all contact with other people, beacuse I knew the first words out of my mouth were going to be "do you have any cubes?"

Then I got to 7-11 and went on my search. It was down to condom boxes and bars of soap. I thought that using boxes of condoms would be funny, but it takes 4 of them to make a good cube shape, and i didn't want to be seen walking around with that many condoms. Instead, I elected for the boxes of soap because I actually needed soap. But then a guy who worked there saw me walking around with like--well, alot of--bars of soap and asked if I was going to some kind of soap party. I glanced at the awkward stack of soap towering from my arms to my neck and tried to figure out a way I could explain it, but eventually just settled on "its a long story," hoping he wouldn't take offense to my vaguery. I figured I'd rather him think I'm going to some kind of soap fetish orgy than explain what I'm actually going to do with it. That reminds me: I forgot to open up any of the boxes before I taped the paper over it ( the paper is for labeling the axis) so I'm actually still running out of soap.

Saturday I went to Staples and found a lot of $1 cardboard boxes that come in the perfect cube shape. I mean, as perfect as you can get without being that stuffed-animal cube thing from think geek. If I had known this was going to take more than a week I would have ordered a few. I also found this giant $30 tablet of poster-board-sized sheets of paper that you can use dry erase markers on. Then I got home and discovered that the tablet was actually just well-marketed and contained only a single dry erase surface, which I filled up immediately, as well as some giant sheets of paper I'll probably never use. All I really want are like posters--actually white posters that you can use dry-erase markers on. Whatever. I'm back on paper.

So Paul Oakenfold and me have been at this all weekend, save for tiny breaks like seeing Iron Man 2. There is a brief flash of a 4D hypercube, by the way, when Tony Stark is flipping through his fathers notebook. It actually makes no sense why there would be a hypercube in the notebook, but the entire subplot about synthesizing a new element actually makes no sense anyway. And I am starting to hear the same Oakenfold songs over again too many times. I may have to switch to Armen Van Buren. I need to wait until the algorithm is done though; I don't have nearly enough Armen Van Buren tracks to carry me the rest of the way.

Writing my solution in java turned out to be ridiculously tedious; it must be one of the most inefficient programs for transcribing algorithms. Everything is so simple in my head, and then I go to write it down and it turns into pages and pages of java code. Although, I did have to create some multi-dimensional cube-projection-thingy data structures, so I guess thats why.

I realize that the chances of me actually solving something that generations of smarter people have failed to solve are slim. The only things that make it plausible are the fact that most people think P != NP, and therefore aren't even trying, and the fact that maybe nobody loves hypercubes as much as I do. I actually tried to make a Neverwinter Nights campain involving a 4 dimensional tower. It was going to be awesome. Then I realized that 3^4 is 81, and the cool-looking gargoyle statues killed me every time I tried to playtest it, so I gave up.

I'm also skeptical that its possible for me to win a million dollars. Like that would change my life too much. I went for a walk today, though, to cool my brain off, and thought about what I could spend it on. There's always a plane capable of more than 300 knots so I can visit philly whenever I want. Then, I was thinking I'd buy the rights to Duke Forever and get that finished. Thats as far as I got. I actually don't care about the money as much as being able to write "solved 3sat in polynomial time" in the little application we use for reporting days off. I'm not excited though; I've been disappointed too many times to think I can actually solve this. The only reason I keep going is because I haven't failed yet. And because I can't think about anything else. Well, girls. But besides that I can't focus on anything else.

Anyway, I am mentally and even physically exhausted (lots of pacing around while playing with a deck of cards), as well as probably malnurished and dehydrated. I've had a lot of caffeine though. But I'm going to see this through. I just got to the fun part of the algorithm when I lost my concentration and had to call it a night. I'm gonna keep at it as soon as I get up tomorrow. I am so anxious too--at this point I won't really know if it works until I get the programming running and solve all possible 3-Sat problems with 4 and 5 variables--if I can. I remember that being a big number. I think 3-sat with less than 5 variables is a special case though.

If you posses any good sample data, feel free to send it to me. Better yet, send me a really big 3-sat problem that today's computers would take a week so solve, and we'll see how fast I can do it. My algorithm runs in about m^3 where m is the number of variables.