# Relations between deciding languages and computing functions in advice machines 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 $$\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. Posted on Categories proxies