Inspired by this [answer][1] given by Noam, which (I think) implies that a set $A \in NP$ if and only if there is polynomial-time computable function $f$ from random strings to elements of $A$ such that $A$= $\{ a: f(x)=a, x \in S \}$ where $S$ is the set of all witnesses $x$ for set $A$. If P=NP then every coNP set is _efficiently samplable_ in Noam's sense.


The following characterization of NP is taken from [Theory of computational complexity][2];

"A binary relation $R \subseteq\Sigma^* \times \Sigma^*$ is called polynomial honest if there exists a polynomial function $p$ such that $<x,y> \in R$ only if $|x|\le p(|y|)$ and $|y|\le p(|x|)$. A function $f:\Sigma^* \to \Sigma^*$ is polynomially honest  if the relation $\{ <x, f(x)>: x\in \Sigma^*\}$ is polynomial honest. 

Therefore, $A \subseteq \Sigma^*$ is in $NP$ if and only if $A=Range(f)$ for some polynomial honest and polynomial time computable function $f$."

I am interested in the assumption that there exists a _universal witness set_ $W \in P$ for $NP$. A set $W \in P$ is universal witness set if for every $NP$-complete set $C_i \subseteq \Sigma^*$ there is some polynomially honest and polynomial-time computable function $f_i:W\to \Sigma^*$ such that $C_i=Range(f_i)$. Equivalently, every $NP$-complete set is definable by a relation $<f_i(w), w>$ for $w \in W$.

> When does the existence of a _universal witness set_ for $NP$ implies the impossibility of _efficient sampling_ of $coNP$ sets? Can we prove the implication if function $f_i$ is length-increasing injection? Has anyone studied similar notions to _efficient sampling_ characterization of $NP$?


Some evidence suggests the existence of universal witness set for $NP$. Oded Goldreich states the fact that "all known reductions among **natural** $NP$-complete problems are either parsimonious or can be easily modified to be so". ( [Computational Complexity: A Conceptual Perspective By Oded Goldreich][3]). Also, [Yato and Seta][4] define parsimonious ASP-reductions and state that $ASP$-completeness imply $NP$-completeness (Page 2, second paragraph). Their ASP-reduction requires efficiently computable bijections between solutions sets.




[1]: http://cstheory.stackexchange.com/a/567/495
[2]: https://books.google.com.sa/books?id=oG6lRcwRqCUC&pg=PA71&dq=%22polynomially+honest%22++%22honest+function%22&hl=en&sa=X&ved=0CCkQ6AEwAmoVChMI9snDzO7kxwIVxH4aCh0A8AjC#v=onepage&q=%22polynomially%20honest%22%20%20%22honest%20function%22&f=false
[3]: http://books.google.com.sa/books?id=EuguvA-w5OEC&pg=PA204&lpg=PA204&dq=natural+problem+parsimonious+reduction&source=bl&ots=ORhA93Hr6i&sig=3Oi_F70aiaVOZ2aYlQENBteqwV4&hl=en&sa=X&ei=dUBeVK3oHbGu7Abui4DQBQ&ved=0CB0Q6AEwAA#v=onepage&q=natural%20problem%20parsimonious%20reduction&f=false
[4]: http://www-imai.is.s.u-tokyo.ac.jp/~yato/data2/SIGAL87-2.pdf