<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.)</p>
<p>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 <span class="math-container">$P$</span> is the set of languages decidable in polynomial time. I'll think of languages in <span class="math-container">$P$</span> as the analogues of open sets and polytime-computable functions (which will serve mainly as <em>reductions</em>) as the analogues of continuous functions.</p>
<p>Note that <span class="math-container">$P$</span> is closed under complement, finite union, and finite intersection, but not countable union or intersection (breaking the analogy).</p>
<p>Now in analogy with continuous functions, consider all <em>polytime</em> functions: functions <span class="math-container">$f: \Sigma^* \to \Sigma^*$</span> that are computable in polynomial time. You might also want to require that its input and output sizes are polynomially related (<em>i.e.</em> for some <span class="math-container">$p$</span>, <span class="math-container">$|x| \leq p(|f(x)|)$</span>). This choice could alter the sequel a little, so that's a caveat, but the whole discussion is sub-formal anyway.</p>
<ol>
<li><p>We can see that the polytime functions satisfy the following property: <span class="math-container">$B \in P \implies f^{-1}(B) \in P$</span>. 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.</p>
</li>
<li><p>We can also see that a language <span class="math-container">$B$</span> is in NP if and only if it is the polytime image of a language in <span class="math-container">$P$</span>, that is, there exists <span class="math-container">$A \in P$</span> and polytime <span class="math-container">$f$</span> with <span class="math-container">$f(A) = B$</span>.</p>
<p>Sketch: If <span class="math-container">$A \in P$</span>, then to decide the language <span class="math-container">$f(A)$</span> in nondeterministic polynomial time, given <span class="math-container">$y$</span>, guess <span class="math-container">$x$</span> and accept iff <span class="math-container">$f(x)=y$</span>. On the other hand, if <span class="math-container">$B$</span> is in NP, let <span class="math-container">$A = \{(x,w) : x \in B \text{ and $w$ is an NP certificate for $x$}\}$</span>. <span class="math-container">$A$</span> is decidable in polynomial time and the polytime function <span class="math-container">$f$</span> that projects onto the first element of the pair satisfies <span class="math-container">$f(A) = B$</span>.</p>
</li>
<li><p>Therefore, we can notice that <span class="math-container">$P = NP$</span> if and only if <span class="math-container">$P$</span> is closed under these polytime mappings, i.e. for all <span class="math-container">$A \in P$</span> and polytime <span class="math-container">$f$</span>, <span class="math-container">$f(A) \in P$</span>. The analogous statement in topology would be &quot;all continuous mappings are open mappings&quot;.</p>
</li>
<li><p>We can see that an NP-complete set <span class="math-container">$B$</span> has the property that, for <em>every</em> <span class="math-container">$A \in P$</span>, there exists a polytime <span class="math-container">$f$</span> with <span class="math-container">$f^{-1}(B) = A$</span>. If <span class="math-container">$P \neq NP$</span>, then an NP-intermediate set <span class="math-container">$C$</span> would therefore satisfy that there is some <span class="math-container">$A \in P$</span> with, for every polytime <span class="math-container">$f$</span>, <span class="math-container">$f^{-1}(C) \neq A$</span>; and also that it is not decidable in polynomial time, so there is no <span class="math-container">$A \in P$</span> and polytime <span class="math-container">$f$</span> with <span class="math-container">$f^{-1}(A) = C$</span>.</p>
</li>
</ol>
<p>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;<span class="math-container">$P = NP$</span> 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;).</p>
<p>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).</p>
<p>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 <span class="math-container">$P$</span> and <span class="math-container">$NP$</span>; one might also think of e.g. <span class="math-container">$DTIME(g(n))$</span> for a specific <span class="math-container">$g$</span>; I'm not sure if that's interesting.</p>

CC BY-SA 3.0
2014-03-30T04:20:52.533Z
Re 2, we can always assume that $A = \emptyset$ or $A = \Sigma^*$. Put differently, if $B$ is non-empty then we can always take $A = \Sigma^*$.
Yuval Filmus
CC BY-SA 3.0
2014-03-29T22:42:40.333Z
2014-03-30T05:54:31.170Z
2020-06-17T09:38:08.363Z
usul
<p>Inspired by this <a href="https://cstheory.stackexchange.com/a/567/495">answer</a> 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$.</p>

<p>This motivates studying the properties of the space $S$ (of all witnessing strings $x$) for various $NP$ problems. </p>

<blockquote>
  <p>Is there a published work that studies space $S$ for various problems inside $NP$ such as $P$ problems, $NPI$ problems, and $NP$-complete problems?</p>
</blockquote>

<p><strong>UPDATE 9/7/2015:</strong></p>

<p>The following formalism is taken from <a href="https://books.google.com.sa/books?id=oG6lRcwRqCUC&amp;pg=PA71&amp;dq=%22polynomially+honest%22++%22honest+function%22&amp;hl=en&amp;sa=X&amp;ved=0CCkQ6AEwAmoVChMI9snDzO7kxwIVxH4aCh0A8AjC#v=onepage&amp;q=%22polynomially%20honest%22%20%20%22honest%20function%22&amp;f=false" rel="nofollow noreferrer">Theory of computational complexity</a>;</p>

<p>"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. </p>

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

<p>Now, assume that there exists a <em>universal witness set</em> $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)$.</p>

<blockquote>
  <p>What are the consequences of existence of a <em>universal witness set</em> for $NP$? Does it imply $P \ne NP$?</p>
</blockquote>

<p>The last question is interesting only when the <em>universal witness set</em> $W$  is in $P$ (3SAT can be seen as universal witness set but it is not known to be in $P$). </p>

CC BY-SA 3.0
2014-03-29T20:28:00.163Z
It seems that $A=f(S)$. To get NP you need the fact that S is in P (let $f$ be id).
Kaveh
CC BY-SA 3.0
2014-03-29T22:31:57.143Z
I don't understand well what $S$ is. For example, what is $f$ for $SAT$?
Marzio De Biasi
CC BY-SA 3.0
2014-03-29T22:49:16.767Z
One way to resolve this, summarizing bits of my answer, is that for SAT you could take $S$ to be the set of pairs $(a,w)$ where $a \in SAT$ and $w$ is the witness. Then $f((a,w)) = a$.
usul
CC BY-SA 3.0
2014-03-29T23:19:51.963Z
You also need to require that $f$ does not 'shrink' its inputs too much i.e. $|f(x)| \ge |x|^c$ for some $c>0$ and all sufficiently large $x$. This corresponds to saying the witness sizes are polynomial in the input size. Without this constraint, even non-computable languages like the halting problem can be expressed this way!
Thomas Steinke
<cc.complexity-theory><reference-request>
Universal witness set for $NP$
Mohammad Al-Turkistany
# Universal witness set for $NP$

(Asked by: username_0 on 2014-03-29)

Inspired by this [answer](https://cstheory.stackexchange.com/a/567/495) 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](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);

"A binary relation $R \subseteq\Sigma^\* \times \Sigma^\*$ is called polynomial honest if there exists a polynomial function $p$ such that $ \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\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$).

**Tags:** cc.complexity-theory, reference-request

> **Comments:**
> **username_1**: It seems that $A=f(S)$. To get NP you need the fact that S is in P (let $f$ be id).  
> **username_2**: I don't understand well what $S$ is. For example, what is $f$ for $SAT$?  
> **username_3**: One way to resolve this, summarizing bits of my answer, is that for SAT you could take $S$ to be the set of pairs $(a,w)$ where $a \in SAT$ and $w$ is the witness. Then $f((a,w)) = a$.  
> **username_4**: You also need to require that $f$ does not 'shrink' its inputs too much i.e. $|f(x)| \ge |x|^c$ for some $c>0$ and all sufficiently large $x$. This corresponds to saying the witness sizes are polynomial in the input size. Without this constraint, even non-computable languages like the halting problem can be expressed this way!  

---

## 1 answers

### Answer by username_3 on 2014-03-29. Score: 4

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 "extended comment", 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 "universe". In analogy with a topology, we can define a sort of "computational space" 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.

1. 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 "continuous" 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.
2. 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$.
3. 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 "all continuous mappings are open mappings".
4. 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: "$P = NP$ if and only if every polytime mapping can be preimaged in polynomial time", (the analogy is that "every continuous function has a continuous inverse").

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.

> **Comments:**
> **username_5**: Re 2, we can always assume that $A = \emptyset$ or $A = \Sigma^*$. Put differently, if $B$ is non-empty then we can always take $A = \Sigma^*$.  

---

