Wrong Again

n is the number of variables. y is the number of seconds my algorithm took to solve 1000 problems with 4.24*n clauses. n^3 and n^2 are there to make me feel better because currently y happens to sit between them.

n	y	0.1n^3	0.1n^2
32	198	3276.8	102.4
40	366	6400	160
48	761	11059.2	230.4
56	1232	17561.6	313.6
64	2507	26214.4	409.6
80	7138	51200	640
96	18468	88473.6	921.6

I tried to find a "least squares for dummies" web page but instead got this calculator, according to which my function could be n^2, n^3, n^4, or exponential.  Any of them can be made to fit the data.

What worries me is that my algorithm has been working on a problem of size n=150 for at least 36 hours and has not solved it yet.  If you extrapolate 36 hours per problem to 1000 problems, that number does not fit well in my little table, so perhaps y will blow right past n^3.



[1] http://people.hofstra.edu/Stefan_Waner/newgraph/regressionframes.html


---------------------------

Yeah all that is what I would have written.  Today I and a friend were bored at work so I asked him about least squares regression (I know, I know...) and we got into my description of "logarithmic number of exponential steps" and then he pointed out that it is not, in fact, cn*2^log(n) but actually more like cn*n^log(n).   Turns out that is a big fucking difference.  I believe that my algorithm is, or can be, polynomial time, but now I no longer have an upper bound.  Are those figures in my table exponential?  Could be.  As I probably wrote already, you can fit any equation you want to data using least squares.  SAT is a cruel mistress...the simplest of operations, like set intersection, can cause an explosion in the complexity of your representation of the problem.

In summary...I need to get a fucking life.  Seriously I'm sitting in my bedroom on a tuesday night and I can't think of anything to do.  I will probably just boot up my starcraft partition and play some games, idk.