3 to the S to the A to the T, bitch

The move was horrific, and I wrote page of notes of things I wanted to mention in what I thought would be an epic post.  Too bad I'm too lazy to write an epic post.  It was bad, though.  Like so bad I'm kind of surprised all of my stuff even made it to the new place.  Anyway.

3-SAT.  Stop reading if you don't have some kind of math degree.  I mean, sure, you're welcome to continue, but don't blame me if you don't understand something and don't go thinking that I'm a big fucking nerd just because I can't stop trying to solve the biggest math problem in computer science.

I was bored at work one day...perhaps one day last...was it in a meeting?  I don't know.  I was just...sitting around.  Got another idea for 3 sat.  I was inspired by some random snippet I read on the web about how solving NP-Completeness would probably mean solving NP-Hardness, because you could just solve a polynomial number of NP-Complete problems in order to solve the NP-Hard one.  I don't really care about that;  NP-Hard can go fuck itself.  But it did lead to an interesting idea.

It was an idea that I pursued for at least two weeks, running into road blocks, coming up in new ideas...until I had enough of an idea to turn into code.  Then I kept daydreaming about it at work and going home to tweak it at night.

Aaaand it didn't work.  I tried over and over to make it work but I just couldn't get it to polynomial time.  In fact, some of my ideas for making it work better actually made it worse...far worse.  Like doing a polynomial number of reductions to 2-sat.  That bombed.  Then, while I was just messing around, I tried something that should not have worked at all, and it solved 3-sat faster than anything I've ever tried before.

I never did come up with a polynomial method of solving it...but I do appear to have invented an exponential operation that gets run a polynomial number of times.  Something like O(2^(log(n))-ish*.  I have no idea why it works.  It just does.

I've begun spot-checking the algorithm against a few instances in satlib but my heart is not really in it.  This is the high part of a 3-sat addiction, the part where I daydream about being famous and money and selling t-shirts that say "P=NP" on them.  What comes next is the moment I crash and realize my algorithm cannot solve all instances of 3-sat.  I hate that part.  It is the exact same feeling as hooking up with an amazing girl you want to keep and then getting a text about just being friends.

I suppose next up is more testing.  Instances with 125 variables are sort of right on the edge of my attention span.  Maybe I will spin off a map reduce job to solve every problem in satlib.  Maybe write a generator;  I don't know.  The problem space is too enormous, but maybe I will happen to generate an instance that will break my algorithm.  Right now it is programmed to print "FAIL" if it is unable to solve an instance before using up all log(n) of operations that I've alotted it.


*have not thoroughly analyzed the runtime yet...probably more like O(2^log(n) * n^c) or something.