Correct to characterise NP set as P-time image of P set? - MathOverflow

Correct to characterise NP set as P-time image of P set?

2010-08-07T13:18:40Z

[I'm not familiar with the terminology, so when I write P (resp. NP) set, I mean a subset of the integers whose membership function is a decision problem in P (resp. NP).]

Is it correct to say that a set is NP if and only if it is the image of a P set under a polynomial time function?

This seems fairly clear to me: the P set acts as the collection of verification certificates for the elements of the NP set. I'm not particularly familiar with the field though, so I wanted to check.

Answer by Joel David Hamkins for Correct to characterise NP set as P-time image of P set?

2010-08-07T13:32:32Z

Every NP set is realized that way. And the characterization is correct in both directions if you add the stipulation that $f(b)$ and $b$ are polynomially related in size.

First, every NP set is a polytime image of a set in P. If a set $A$ is in NP, then there is a $P$-time decidable set $B$ of pairs (a,b) such that $a\in A$ if and only if there is $b$ such that $(a,b)\in B$. (And where the size of $b$ is polynomially restricted by the size of $a$ for all pairs in $B$.) Let $f$ be the function mapping (a,b) to a. Thus, $A$ is the image of $B$ under $f$, as desired.

~~Conversely, any P-time computable image of a P-time decidable set is in NP, since if $A$ is the image of $B$ under $f$, then $a\in A$ is witnessed by some $b$ such that $f(b)=a$.~~

Conversely, if $A$ is the image of an NP set $B$ by a function $f$ for which $f(b)$ and $b$ are polynomially related in size, then $a\in A$ is witnessed by $b$ such that $f(b)=a$.

Ryan's answer shows that an additional assumption on $f$ is required.

Answer by Ryan Williams for Correct to characterise NP set as P-time image of P set?

2010-08-07T16:08:38Z

No. In particular, the images of sets in $P$ under polynomial time reductions contain many more sets than $NP$. Below I show that the halting problem is among them.

Let {$M_i$} be a list of all Turing machines. Let $f$ be a mapping from {$M_i$} $\times$ {0,1}* $\times$ {0,1}* to {$M_i$} $\times$ {0,1}* , such that

If $H \in~$ {0,1}* is a valid computation history that witnesses $M_i$ on $x$ halt, then $f(M_i,x,H) = (M_i,x)$. More precisely, a configuration of $M$ on $x$ is a bit string encoding the entire status of the computation at some step of $M$ on $x$: it encodes the currrent head position, the current non-blank tape contents (finite), and the current state of $M$. $H$ encodes a chronological list of every configuration of $M$ on $x$, starting from its initial configuration to its halting configuration. ($H$ could be very, very long, but it is finite, provided that $M$ halts on $x$.)
Otherwise, $f(M_i,x,H) = (M,0)$ where $M$ is a fixed Turing machine that halts on input $0$. We can hard-code such an $M$ into a polynomial time computable function, as it is of constant length.

Observe that $f$ is polynomial time computable! If $H$ is actually valid, then we have all the information we need to determine if $M_i(x)$ halts: the length of $H$ is at least the number of steps needed for $M_i(x)$ to halt. If $H$ isn't valid, then we can determine this by finding two adjacent configurations on the list such that the "next" configuration doesn't follow from the "previous" configuration. Each of these have length at most $|H|$ and checking the property amounts to checking a constant number of bits in each configuration: since $M_i$ is a Turing machine, at most a constant number of bits of the tape (and its current state) are manipulated in every step.

However, it is clear that the image of this polynomial time mapping is precisely the halting problem: the list of all pairs $(M_i,x)$ such that $M_i$ halts on $x$.

The gap in Joel's proof in the converse direction: the problem is that $a$ may be much much smaller in length than $b$.