In the section on blind tansformation the claim is made that blindly applying the Gray code will not help the average search time, even when the set of functions is restricted to those in the closure obtained by applying the code 2n times. Suppose we have a function and an algorithm such that on all but one of the functions obtained by applying the Gray code the algorithm takes quadratic time. On that last function it takes exponential time. Since the closure has only 2n functions, the average time will also be exponential.
Now we run our algorithm in parallel on 2n processors, stopping when the first solution is found. Thus, we will stop after only quadratic time and the processor-time(pt) product is cubic. Since we can emulate our parallel algorithm in O(pt) = O(n^3) time using standard techniques, haven't we contradicted our futility claim?
In the section comparing NFL to NP, a classification of knowledge of coloring based on an adversary that returns the number of colors used by the greedy algorithm for a given permutation is outlined. It is hinted in a previous paragraph that a myopic adversary might also return the color assigned to each vertex by the adversary. Assume such a myopic adversary and show that evaluating only a quadratic number of permutations is sufficient for a clever algorithm to find the complete structure of the graph, and thus to be able to find the chromatic number as in the first class.
Continuing this line of thought, can an algorithm fighting a second class adversary determine the complete structure of an arbitrary graph given only the number of colors used?
In their paper on simulated annealing, Johnson et al (search for jams91 in the Graph Coloring bibliography) partition the graph vertices and evaluate the partition according to the number of conflicts induced by the partitioning. Design a knowledge classification based on an adversary that reutrns the number of conflicts and extend it to arbitrary problems.