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 $T_1$ machine 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 $langlecdot,cdotrangle$ 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,rrangle}$ 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.