8 Nov
2000
8 Nov
'00
9:11 a.m.
On Sat, 4 Nov 2000, dmolnar wrote:
The original problem for which this was shown was formula satisfiability: "given a boolean formula, does there exist an assignment to all of its variables which makes the formula evaluate to true?"
Wasn't it that quite a number of actual instances of this particular problem
fall easily to heuristics? Is this connected to the concept of "uniform
hardness" that was brought up?
Sampo Syreeni