1
$\begingroup$

I'm trying to understand implications of translating between functions and languages for P/Poly complexity. I'm not sure whether the following all makes sense. Giving it my best shot given my current understanding of the concepts. (I have a project in which I want to discuss Hava Siegelmann's analog recurrent neural nets, which recognize languages in P/Poly, but I'd like to understand and be able to explain to others implications this has for computing functions.)

Suppose I want to use an advice Turing machine $T_1$ to calculate a function from binary strings to binary strings $f: \{0,1\}^* \rightarrow \{0,1\}^*$. $T_1$ will be a machine that can compute $f$ in polynomial time given advice that is polynomial-size on the length of arguments $s$ to $f$, i.e. $f$ is in P/Poly. (Can I say this? I have seen P/Poly defined only for languages, but not for functions with arbitrary (natural number) values.)

Next suppose I want to treat $f$ as defining a language $L(f)$, by encoding its arguments and corresponding values into strings, where $L(f) = \{\langle s,f(s)\rangle\}$ and $\langle\cdot,\cdot\rangle$ encodes $s$ and $f(s)$ into a single string.

For an advice machine $T_2$ that decides this language, the inputs are of length $n = |\langle s,f(s)\rangle|$, so the relevant advice for such an input will be the advice for $n$.


Question 1: If $T_1$ can return the result $f(s)$ in polynomial time, must there be a machine $T_2$ that decides $\{\langle s,f(s)\rangle\}$ in polynomial time? I think the answer is yes. $T_2$ can extract $s$ from $\{\langle s,f(s)\rangle\}$, and then use $T_1$ to calculate $f(s)$, and then encode $s$ with $f(s)$ and compare it with the original encoded string. Is that correct?


Question 2 (my real question): If we are given a machine $T_2$ that can decide $\{\langle s,f(s)\rangle\}$ in polynomial time, must there be a way to embed $T_2$ in a machine $T_3$ so that $T_3$ can return $f(s)$ in polynomial time?

I suppose that if $T_2$ must include $T_1$, then the answer is of course yes. $T_3$ just uses the capabilities of $T_1$ embedded in $T_2$ to calculate $f(s)$. But what if $T_2$ decides $L(f)$ some other way? Is that possible?

If we are given $s$, we know its length, but not the length of $f(s)$. So in order to use $T_2$ to find $f(s)$, it seems there must be a sequential search through all strings $s_f = \{\langle s,r\rangle\}$ for arbitrary $r$. (I'm assuming that $f(s)$ is unbounded, but that $f$ has a value for every $s$. So the search can take an arbitrary length of time, but $f(s)$ will ultimately be found.)

One thought I have is that the search for a string $s_f$ that encodes $s$ with $f(s)$ has time complexity that depends on the length of the result $f(s)$ (plus $|s|$, but that would be swamped when $f(s)$ is long).

So now the time complexity does not have to do with the length of the input, but only the length of $f(s)$. Maybe $L(f)$ is in P/Poly if $f$ is in P? (Still confused here.)

Thinking about these questions in terms of Boolean circuits has not helped.

$\endgroup$
  • $\begingroup$ Thanks @DW. I thought I'd caught all of the typos. All fixed now, or at least closer to the limit. ("advice Turing $T_1$ machine" was supposed to be "advice Turing machine $T_1$".) $\endgroup$ – Mars Jul 24 at 16:55
1
$\begingroup$

I think the answer to Question 2 is "no", as far as we know. For instance, let $f$ be the function that parses its input $s$ as a 3CNF formula $\varphi$ and then returns the lexicographically earliest satisfying assignment to $\varphi$, or $\bot$ if none exists. Then it is easy to decide $L(f) = \{\langle s,f(s) \rangle\}$ in polynomial time, but (assuming P $\ne$ NP), you cannot compute $f$ in polynomial time (and assuming P/poly $\ne$ NP, advice doesn't help).

The following might be a better way to translate between functions and languages. Let $L'(f) = \{\langle s,i,b \rangle : f(s)_i=b\}$, where $y_i$ denotes the $i$th bit of $y$. (I assume that if $y$ has fewer than $i$ symbols, then $y_i=\bot$.) Then if you can compute $f$ in polynomial time, you can decide $L'$ in polynomial time; and if you can decide $L'(f)$ in polynomial time and the length of $f(s)$ is polynomial in the length of $s$, then you can decide $L'(f)$ in polynomial time.

| cite | improve this answer | |
$\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.