Which randomness models in particular? The two Erdős–Rényi models G(n,p) vs G(n, M)? I thought for almost all purposes they gave the same answer as long as equivalent M and p were chosen in the large n limit, because the concentration around M will be so tight due to the law of large numbers. Is there some other model you're looking at?

Random without qualification is used to mean "uniformly". For this specific case (3-SAT), there are only four reasonable readings: both (variables within a clause), and (clauses within the set of all possible clauses) can be chosen with or without replacement. Neither makes a difference in the large n limit.

http://books.google.com/books?id=zyktZTqZSzMC&lpg=PA414&...

is from a reasonable book.

It's true that this phenomenon hasn't been completely rigorously proven, but it's been given "physicist proofs". There's enough evidence that it's unreasonable to not consider it true.

My sense is that there are hard 3-coloring problems in graphs that don't look "random". Certainly the ones I generate have a small number of vertices with very high degree, and the others are more reasonable. This is why I say that there are potentially things happening with different random models. But you are certainly right on all counts.

However, where you say this:

    .... it's been given "physicist proofs". There's enough
    evidence that it's unreasonable to not consider it true.

There had been a lot of evidence around for quite some time that primality was harder than P (assuming P!=NP), and yet it turns out to be in P, even without PvsNP being settled. I'm suspicious. I still believe that hard instances can be found, and that "most" of them will look as you describe, random-ish with the right parameters, but I'm wary about claiming that most things that look like that will, in turn, be "hard."

But I suspect we're in agreement, possibly "violent agreement."

ADDED In EDIT: Forgot to say, thanks for the reference.

Yes, we are in violent agreement then.

Easy to generate random hard instances does not at all mean that highly structured "non-random" instances can't be hard. The "phase transition" only means that the fraction that are hard at a given non-critical ratio decreases with n, but there very well could be a large absolute number, that increases with n. The space of problems of size n grows exponentially, after all.

My sense is that even before AKS, most researchers believed primality was in P. This was based mainly on poly-time probablistic algorithms developed in the 80's.

Here's a Nature article that's pretty readable

http://www.cs.cornell.edu/selman/papers/pdf/99.nature.phase....