My understanding is that if we have a totally random k-SAT formula, for a ratio $m < \alpha n$ far enough below the satisfiability threshold, we can solve for satisfiability in polynomial time (with a high probability of success as $n$ tends to infinity).
What I'm curious about, and which I guess is the beginner's question, is what happens if we increase $k$, $m$, and $n$. To elaborate, we can suppose that the original formula is significantly above the threshold, and therefor no polynomial method is guaranteed. However, the new increase in $k$ puts the formula significantly below the threshold, and so if the new formula was random, it could be solved in time polynomial in the new $n$.
However, the new formula is not random. It's based on the old one. So it seems that the polynomial methods don't apply. My curiosity is, if we could generate several formulas with increased $k$, $m$, and $n$, below the threshold, they may in some way be considered random. So perhaps the randomness criterion can be satisfied. I'm wondering if there is any way to prove this...
Perhaps what I'm really after is finding out what constitutes randomness in satisfiability instances. Of course it's a random formula with the proper parameters, but doesn't this mean that if we can repeatedly generate formulas with the same parameters, they can be considered random?
I'm really hoping that someone can give me a better perspective on things. I keep wondering if there's some way to modify SAT formulas to take advantage of polynomial methods.