[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.



Correct to characterise NP set as P-time image of P set?
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$.


