Archive for August 14th, 2010

A possible answer to my objection

August 14, 2010

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 f is a polynomial-time computable function on n+m bits, where m is at most polynomial in n. Then we can fix a set A of n bits, and for each x\in\{0,1\}^A we can ask the question, “Does there exist y\in\{0,1\}^{A^c} such that f(x,y)=1?” (By (x,y) I mean the sequence that agrees with x on A and with y on A^c.) And we can set g_A(x)=1 if and only if the answer is yes.