The Trillion Instance Algorithm

"It was first suggested that a googolplex should be 1, followed by writing zeros until you got tired."

--Kasner and Newman

 

"And so it came to pass that Ryu, son of Dragon the Shogun, ascended the steps of the great Temple of The Real Projective Plane, and stared into the mobius vortex.  By surviving he earned the right to study with the Don, and learn his mathematics.  And when Ryu, son of the Dragon, left that temple he found the Don's mathematics more powerful than the math of any warrior he encountered, and Ryu laid waste to the land, for in the vortex he had lost his sanity, and for the rest of his life the drum beats in his mind never ceased."

Yeah, anyway.  After scribbling on enough paper to kill a few trees (not that it matters) I came up with a 3-SAT algorithm, and coded it in two days.  This time I am certain that the upper bound is O( n ^ 10 ) but uncertain that it will solve all 3-SAT instances.  With this algorithm, there is no risk of it exceeding the upper bound; it will simply get stuck and sit down in the sand and cry boolean tears.

Obviously,  since programming is, to me, more fun than mathematical proofs, my next instinct was to think about simply solving every 3-SAT algorithm in existence.  I tried calculating an upper bound on the number of 3 sat instances that could exist.  For a problem of 20 variables, the number of possible instances that can exist is a number with hundreds of decimal places.  This might be the first time I've noticed a finite set of things that could not be adequately described by the word fuckload.  Maybe a...oh wow there are actually words that go that high.  So, its less than a centillion, however so much more than a vintigillion that its not even worth comparing.

Anyway.  I don't have the hard drive space to store that many instances, and lets not even talk about the issue with duplicates.

Instead, I am making it my goal to solve a trillion instances with my new algorithm, which doesn't even have a name (other than "Algorithm.cs") because I've just given up naming these things.  All it takes is one boring meeting and another 3-SAT algorithm pops into my head.

Anyway, once I solve a trillion instances...I suppose I would take it more seriously and do the actual legwork to create a proof.  Although, I am much more a fan of this model:

1. Solve one trillion instances
2.  ...
3. Prove P=NP !

Step 2 is actually the same exact step in the standard startup business model:

1.  Cool idea
2.  ...
3. Profit!

So I know I'm not that crazy.  Whatever the case, it's nice to have a distraction.

I'm pretty sure I write a post like this every time I think I've gained traction with one of my 3-SAT ideas.  I'm pretty sure of this because when I was calculated the total number of possible instances, I remembered how to do it because I did it before, and I remembered how I wrote about it last time.  So, welcome to recycled content.