It seems that the informal argument in my previous post may have been aiming off target. Here is a sort of counter to it, by Jun Tarui. (See also this earlier comment of his, and the ensuing discussion.)

If I’ve understood various comments correctly, Deolalikar is making a move that I, for one, had not thought of, which is to assume that P=NP and derive a contradiction. How could that help? Well, it allows us to strengthen any hypothesis we might like to make about polynomial-time computable functions to one that is preserved by projection.

Let me spell that out a bit. Suppose that is a polynomial-time computable function on bits, where is at most polynomial in Then we can fix a set of bits, and for each we can ask the question, “Does there exist such that ?” (By I mean the sequence that agrees with on and with on ) And we can set if and only if the answer is yes.

(more…)