Universal witness set for $NP$ 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 $&lt;x,y&gt; \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 $\{ &lt;x, f(x)&gt;: 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$).
My answer to the question is that I don't know of published work. However, I've recently been thinking a bit about formalizing what I believe is essentially your question, so I'll try to collect some thoughts in the following &quot;extended comment&quot;, hoping that it will be interesting, useful, or spark productive discussion! (Maybe this is already well-known or studied, in which case I apologize.)
Consider the set of all languages on a fixed alphabet; call this the &quot;universe&quot;. In analogy with a topology, we can define a sort of &quot;computational space&quot; as this universe together with a set of languages, i.e. a set of subsets of this universe. In particular $P$ is the set of languages decidable in polynomial time. I'll think of languages in $P$ as the analogues of open sets and polytime-computable functions (which will serve mainly as reductions) as the analogues of continuous functions.
Note that $P$ is closed under complement, finite union, and finite intersection, but not countable union or intersection (breaking the analogy).
Now in analogy with continuous functions, consider all polytime functions: functions $f: \Sigma^* \to \Sigma^*$ that are computable in polynomial time. You might also want to require that its input and output sizes are polynomially related (i.e. for some $p$, $|x| \leq p(|f(x)|)$). This choice could alter the sequel a little, so that's a caveat, but the whole discussion is sub-formal anyway.

We can see that the polytime functions satisfy the following property: $B \in P \implies f^{-1}(B) \in P$. We would like the following to be true: They are the only such &quot;continuous&quot; functions (note that output-size-messiness comes in when attempting to prove this converse). I don't know if it's true and it might even be equivalent to a very hard problem.

We can also see that a language $B$ is in NP if and only if it is the polytime image of a language in $P$, that is, there exists $A \in P$ and polytime $f$ with $f(A) = B$.
Sketch: If $A \in P$, then to decide the language $f(A)$ in nondeterministic polynomial time, given $y$, guess $x$ and accept iff $f(x)=y$. On the other hand, if $B$ is in NP, let $A = \{(x,w) : x \in B \text{ and $w$ is an NP certificate for $x$}\}$. $A$ is decidable in polynomial time and the polytime function $f$ that projects onto the first element of the pair satisfies $f(A) = B$.

Therefore, we can notice that $P = NP$ if and only if $P$ is closed under these polytime mappings, i.e. for all $A \in P$ and polytime $f$, $f(A) \in P$. The analogous statement in topology would be &quot;all continuous mappings are open mappings&quot;.

We can see that an NP-complete set $B$ has the property that, for every $A \in P$, there exists a polytime $f$ with $f^{-1}(B) = A$. If $P \neq NP$, then an NP-intermediate set $C$ would therefore satisfy that there is some $A \in P$ with, for every polytime $f$, $f^{-1}(C) \neq A$; and also that it is not decidable in polynomial time, so there is no $A \in P$ and polytime $f$ with $f^{-1}(A) = C$.


There seem to be lots of sort-of interesting statements we can make, though their novelty/usefulness is probably dubious. For instance, I think something like this is true: &quot;$P = NP$ if and only if every polytime mapping can be preimaged in polynomial time&quot;, (the analogy is that &quot;every continuous function has a continuous inverse&quot;).
Similarly, you could probably translate lots of complexity statements into this framework but with again dubious utility. For instance, one-way functions (although I haven't thought about randomized algorithms...that could be quite interesting).
Final notes: I think the most interesting thing about this framework is that it seems not to relativize. One might of course think about other interesting complexity classes than $P$ and $NP$; one might also think of e.g. $DTIME(g(n))$ for a specific $g$; I'm not sure if that's interesting.