3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ You really want length non-decreasing since otherwise even $\Sigma^*$ isn't in the range of any length increasing function. $\endgroup$ – Yuval Filmus Dec 21 '14 at 0:56
2
+50
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.