## 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.
(more…)