# 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 $<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$).

• It seems that $A=f(S)$. To get NP you need the fact that S is in P (let $f$ be id). – Kaveh Mar 29 '14 at 20:28
• I don't understand well what $S$ is. For example, what is $f$ for $SAT$? – Marzio De Biasi Mar 29 '14 at 22:31
• 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 Mar 29 '14 at 22:49
• 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 Mar 29 '14 at 23:19

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.

• 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 Mar 30 '14 at 4:20