3-SAT Got Me Again

I don't really remember what happened. It is 4:29 now as I write this. I'm pretty sure I've been working on 3-SAT since I got home, and I actually started this morning while I was at work. I don't remember what trigged it...I must have thought I had some kind of inspiration again.

For those of you who don't know what I'm talking about, there is this unsolved problem in computer science: the question is does P equal NP? Well, last time I checked it was unsolved. Its been more than a year since I was in grad school; maybe somebody's already done it. Anyway, to answer the question, you basically have to come up with an easy[1] way to solve the second-hardest[2] (or third-hardest, depending on how you count) problems in computer science, or prove that there is no easy way to solve them. I've heard most computer scientists are pretty sure that these problems have no easy solution, but can't prove it.

After probably 10 or 12 hours on this attempt, I am pretty sure that I will eventually come up with a solution, one way or the other, but I can't prove it. The only thing that makes this attempt different than the others is I'm not trying to come up with a polynomial time algorithm (i.e. the easy way) to solve it. This time, I thought I would just attempt to solve every instance of 3-Sat (for 4 variables) and, you know, see where that took me. You may not know this, but there are a lot of instances of the 3-Sat problem for 4 variables. Like, if you wrote down how many possible 3-Sat problems with 4 variables there are, that number would probably have more than 17 digits. I don't know for sure though. Combinatorics is not my strong spot. In fact I have been cheating and using a calculator.

So, anyway, I did come up with a polynomial time algorithm. In fact, it might be damn near linear. The only problem is, you have to do this tiny little transformation to the 3-Sat problem--just a little...a little thing--and that itty bitty transformation happens to require exponential time (2^m where m is the number of variables in the problem, if you're curious). My giddiness at thinking I could actually be The One to solve P?NP gently faded like the slow realization that a girl doesn't have feelings for you and really can't even stand having you around.

If you're curious at what my solution was, I thought that 3-Sat expressions could be reduced to coordinates in m-dimensional space. More specifically, they are the coordinates for corners of a m-dimensional hypercube. If you fill all the corners, its not satisfiable. This would be a brilliant solution if m-dimensional hypercubes didn't have 2^m corners. So you can solve the problem, probably, just by counting the number of coordinates you get: if end up with less than 2^m coordinates, the problem is satisfiable. If you end up with 2^m coordinates, the problem is not satisfiable. And if you end up with more than 2^m coordinates...well that would mean I have no idea what I'm talking about. My next steps will involve writing lots of boolean expressions all over the place like a crazy man, and attempting to invent magic data structures.

In summary, I have this nagging suspicion that all of the satisfiable instances of 3-Sat can be solved in polynomial time, and all of the non-satisfiable instances of 3-Sat require exponential time to prove they are not satisfiable.

Oh, and if you don't know what a hypercube is, go here and buy this and mail it to me. You still won't understand hypercubes, but I'll have someone to sleep with at night.


[1] "easy way" = polynomial time algorithm
[2] NP-Complete




[Edit]
Here is the combinatorial calculator I've been using. Its actually awesome because it shows the formula.

Also, I did some thinking in the shower, and if there is a way to see if all of the corners on a single plane are required by the 3-Sat expressions in polynomial time, then we have it.

[Edit]
None of this really makes sense anymore. Its like I was high last night, but not really and I've actually never gotten high anyway. I don't know what I'm doing, but I think I can do it in polynomial time.

[Edit]
I am nearly certain I have a polynomial-time solution to 3-SAT. The proof is in my head; I should be able to translate it from English to Math by tomorrow. If I die before then, tell them the proof is on the wall of my apartment. Oh but not the apartment people--I used a sharpie and they're probably not gonna like that.