Inspired by this answer given by Noam, which I think implies (if I understood correctly his answer ) that a set $A \in NP$ if and only if there is polynomial-time computable function $f$ from a strings space $S$ to combinatorial objects in some space $Y$ such that $A$= $\{ a: a=f(x), x \in S \}$. The space $S$ represents the set of all witnesses $x$ of an $NP$ problem $A$.This motivates studying the properties of the space $S$ (of all witnessing strings $x$) for various $NP$ problems. Is there a published work that studies space $S$ for various problems inside $NP$ such as $P$ problems, $NPI$ problems, and $NP$-complete problems?UPDATE 9/7/2015:The following formalism is taken from Theory of computational complexity;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$.Now, assume that there exists a universal witness set $W \subseteq \Sigma^*$ such that for every $NP$-complete set $D_i \subseteq \Sigma^*$ there is some polynomially honest and polynomial-time computable function $g_i:W\to \Sigma^*$ such that $D_i=Range(g_i)$.What are the consequences of existence of a universal witness set for $NP$? Does it imply $P \ne NP$?The last question is interesting only when the universal witness set $W$  is in $P$ (3SAT can be seen as universal witness set but it is not known to be in $P$). 
Universal witness set for $NP$
cc.complexity theory;reference request