The Angels Have the Phone Box

What is the absolute most important thing to be concerned about when trying to prove P=NP?  Is it the rigor of your mathematical proof?  The soundness of your implementation?  The depth of your testing?  Is it the peers who review your work?  Your sample size?  No.  It is none of these things.  The absolute most important thing you need to worry about is making your implementation play the "Job's done!" clip from the video game Warcraft II [1] [2] [3] [4].

Now that...hey it just finished another batch!  Anyway, now that...now I forget what I was going to say in this paragraph.

Generating a million instances for a SAT instance with 16 variables (and running a brute-force solver to count the number of solutions for each one) took more than a day.  So, obviously ramping that up by a thousand is going to take years.  I don't want to be one of those guys that spends ten years on a hair-brained polynomial time algorithm to post on the internet and get laughed at.  I want to be the guy who spent slightly less than maybe a month on a hair-brained polynomial time algorithm to post on the internet.  Corollary:  I don't have a thousand computers.

I do have one desktop with 4 cores, an old desktop with fried video cards thanks to my bitcoin endeavours, an old eepc that was filled with viruses because of unprotected surfing, and an apple air that I bought to make working from home more productive shortly before finding a new job at possibly the only company on the planet where I am never going to be able to work from home on a computer made by apple.  Oooh!  There it goes again!

Anyway, ...once again I forget--oh right.  So one idea I have, partly thanks to my failed bitcoin experiments (never spend a thousand dollars on top of the line graphics cards that each require two power connectors and then try to save $40 on a cheap power supply two weeks before the bitcoin market crashes), is to write some cuda (or whatever) code and use some GPUs to do the work.  The difference between the CPU and GPU for bitcoin mining was incredible, and I believe that SAT could be equally paralellizable.  I would want to be personally, absolutely certain that I was right about this thing before doing that, though, because that is a lot of work an I'm lazy.


Anyway, I think I'm going to break down the trillion problems into four categories:

1. Breadth Testing:   Tiny problems (16ish variables) - SAT and UNSAT instances - c/v in [2.5,6.02] ?
2. Breadth Testing:   Small problems (20ish? variables) - UNSAT only - c/v in [3.26,5.26] ?
3. Targeted Testing:  Small problems, UNSAT only in [2.5,3.26] and SAT only in [4.26, something]
4.  Depth Testing:  Medium problem (50?  100?) at c/v = 4.26.  Skip brute force checks ahead of time.


Where c/v is clause to variable ratio.  Small and tiny problems will probaby have to be well under 30 variables, because that is when the time required for a simple brute force solver gets ridiculous.  Unless I utilize GPUs.

#3 might be the most useful.  Unless I'm an idiot, my algorithm is guaranteed to stay within O(n^10), and, in fact, can only reach n^10 IFF the instance is UNSAT.  The only danger is reaching a stage before then where the algorithm cannot continue.  I have a fuzzy idea in my head that it will never reach this point.  Solving a trillion instances would give enough credence to that fantasy to try to prove it.