Characterizing the range of a polytime function

Question

Is it true that an infinite language is in P iff it is the range of a length increasing polytime function? I ask because I know that it is a basic result in computability theory that a set is recursive iff it is the range of an increasing recursive function and I was wondering if there might be an analogue in complexity theory.

I know that the "length increasing" (or at least monotone increasing) is a necessary one because otherwise we could construct the Halting Problem: Just have a polytime algorithm test computation histories for a given Turing machine $M$ on input $x$ and map valid halting ones to $(M,x)$. I also know that every language in P reduces to any NP-complete language and these languages are not in P (unless of course P=NP), but I think my question might be different: I am interested in the exact image of a function over ${\Sigma}^{*}$ and not if it happens to be properly contained in an NP-complete set. However, I don't know where to go from there. I would greatly appreciate any hints or counterexamples to demonstrate that my conjecture is false. Thanks.

Answer 1

Your statement (with length increasing replaced with length non-decreasing and with functions allowed to return $\bot$, i.e. nothing) is equivalent to $\mathsf{P}=\mathsf{NP}$.

We start with two observations:

1. Every language in $\mathsf{P}$ is trivially the image of a length non-decreasing function (that's why we allow returning $\bot$).
2. If $f$ is a length non-decreasing polytime function then $y$ is in the range of $f$ iff there exists $x$ of length at most $|y|$ such that $f(x) = y$, and so the range of a length non-decreasing polytime function is always an $\mathsf{NP}$ set.

If $\mathsf{P}=\mathsf{NP}$ then the range of a length non-decreasing polytime function is always in $\mathsf{P}$, and so your (modified) statement is correct.

Suppose now that $\mathsf{P} \neq \mathsf{NP}$. Consider the language $\mathsf{SAT'}$, obtained from $\mathsf{SAT}$ by padding a formula of length $n$ with $n$ zeroes. The language $\mathsf{SAT'}$ is still $\mathsf{NP}$-complete and so not in $\mathsf{P}$. On the other hand, it is in the range of a length non-decreasing polytime function: the polytime function accepts a formula $\varphi$ and an assignment $x$, and if $x$ satisfies $\varphi$ it outputs the padded version of $\varphi$.

---

As I mentioned, you to allow the function to not decrease the length if you want $\Sigma^*$ to be the range of some function. On the other hand, the reasoning above works as long as the function doesn't decrease the length by too much: any polynomial amount (which could depend on the function!) would work.

You can also get rid of $\bot$ if you assume that the languages you consider are not too (efficiently) sparse, that is, given a length $n$, one can find in polytime some word in the language of length at least $n$. This is the correct counterpart of the condition of being infinite.