# 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 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.

• 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$".)
– Mars
Jul 24 '20 at 16:55

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.