If a set is in NP, there exists a TM M and a polynomial p( ) such that, for each x in S, there is a certificate cx such that M(x,cx) accepts after at most p(|x|) steps. Using M, p( ), and the existence of concise certificates, we must show that S is the range of an honest, polynomially computable function f; in other words, f( ) must produce every element of S and nothing else, and must do so honestly and in polynomial time.
We could define f(y)=x whenever M(x,y) accepts in at most p(|x|) steps and |y| <= p(|x|), i.e., if y is a concise certificate for x. This approach fails for at least three reasons: (i) it leaves f( ) ill-defined, because there could be many different x in S for which the same y is a valid concise certificate (for instance, a truth assignment to n variables is a certificate for a very large collection of possible Boolean formulae); (ii) even if this problem were somehow resolved, it is not clear that f( ) would generate all elements of S; and (iii) there is no obvious way to compute this function, short of searching through all possible strings x until one is found for which M(x,y) accepts -- an exponential-time search. These three observations lead us to a working solution: since all we have time to do is little more than running the checker machine M on one pair of values, we should encode both values into the argument of f( ) -- or rather, since the argument is given, we should regard it as the encoding of a pair of values, just as in a dovetailing argument. Let the enumeration of the two indices be given by the dovetailing (pairing) function <-,->; given an argument y for f( ), we regard it as being produced by the dovetailing function, i.e., we write y=<y1,y2>. Note that this will automatically enumerate every element of Sigma* in each coordinate, so that we shall not have to worry about missing elements of S.
Let z0 be some arbitrary element of S (we can always compute one off-line if needed). Given y=<y1,y2>, we begin by decoding y to recover y1 and y2. Next, we check whether |y2| <= p(|y1|); if so, then we run M(y1,y2) for at most p(|y1|) steps. If M accepts, then we set f(y)=f(<y1,y2>)=y1 -- because we have established that y2 is a concise certificate for y1 and thus that y1 is an element of S. If either test fails, we set f(y)=z0.
By construction, it is clear that the range of f is contained in S and that f can be computed in polynomial time (assuming that we can decode the dovetailing pair in polynomial time, which is easy). We are left to verify that every element of S is in the range of f( ) and that f is honest. But both follow immediately from the hypotheses: since every element x to be produced by f is in S which is itself in NP, it has a concise certificate cx; let y=<x,cx>, then it follows that f(y)=x, an honest production of x. (Note that our function is not honest for every single argument: many of the arguments y that lead to f(y)=z0 are such that |y|>p(|z0|); but that does not matter, since at least one of the arguments produces z0 honestly.)