When studying the computational complexity of functions $\{0, 1\}^\ast \to \{0, 1\}^\ast$, is it enough to restrict to $\{0, 1\}^\ast \to \{0, 1\}$?

Question

I started reading Avi Wigderson's paper $\mathcal{P}$, $\mathcal{NP}$ and Mathematics – a Computational Complexity Perspective (link).

(Notation: $\{0, 1\}^\ast$ is the set of all finite binary sequences, and $\{0, 1\}_n^\ast$ is the set of all finite binary sequences of length at most $n$.)

In page 7, he defines the complexity class $\mathcal{P}$: A function $f : \{0, 1\}^\ast \to \{0, 1\}^\ast$ is in $\mathcal{P}$ if there is an algorithm (i.e. a deterministic Turing machine) that computes $f$, and also a constant $c > 0$ such that the number of steps it takes to compute $f(w)$ for any $w \in \{0, 1\}_n^\ast$ is $O(n^c)$.

Immediately after that he says we that we are going to restrict our attention to the boolean functions $f : \Sigma^\ast \to \{0, 1\}$, since "a function with a long output can be viewed as a sequence of Boolean functions, one for each output bit."

I guess he here intends to say something like this: $f : \{0, 1\}^\ast \to \{0, 1\}^\ast$ is in $\mathcal{P}$ if and only if the function $f_i : \{0, 1\}^\ast \to \{0, 1\}$ corresponding to the $i$th output bit is in $\mathcal{P}$ for all $i$.

I find this a bit confusing.

For starters, we are looking at the $i$th output bit, which belongs to $\{0, 1\}$, and we do not have a third symbol to be interpretted as "this bit is empty". This is assuming, of course, that sequences like $0$ and $000\cdots0$ are different. Anyways...

If $f : \{0, 1\}^\ast \to \{0, 1\}^\ast$ is in $\mathcal{P}$, then all of its $i$th bit functions are in $\mathcal{P}$ (forgetting about the empty bit problem for now). For any $w$ of length $\leq n$, we compute $f(w)$ in $O(n^c)$ steps, and extract the $i$th bit in $O(i)$ steps, so the bound for $f_i$ is $O(n + i)$.

We can actually bound the $i$s that will produce an output. The Turing machine that computes $f(w)$ will do at most $O(n^c)$ steps, and so the output will be of length $O(n^c)$. Thus $i$ is bounded above by $O(n^c)$.

For the other direction... Here is what I have thought about: Let $f : \{0, 1\}^\ast \to \{0, 1\}^\ast$ be such that each of its $f_i$ functions are in $\mathcal{P}$. There is nothing saying their complexity have a uniform bound on their polynomial growth, that is, the time complexity for $f_i$ can be $O(n^{c_i})$ with no bound on the $c_i$, or the number of functions that will produce an output (for the time it will take to put all those bits side by side; that still counts, I think).

Any how, so why can this paper focus on complexity for boolean functions only?

EDIT 1: I just noticed something else: In the definition of $\mathcal{NP}$ (definition 2.3), the verifier function $V_C$ is a function $\{0, 1\}^\ast \times \{0, 1\}^\ast \to \{0, 1\}$ not $\{0, 1\}^\ast \to \{0, 1\}$. I can think of ways to make this work (like encoding $(x, y)$ as an element of $\{0, 1\}^\ast$. For instance, $(x, y) \mapsto 1111110xy = 1^{|x|}0xy$, where the number of $1$s gives the length of $x$. The length of the encoding is $2|x| + |y| + 1 \leq |x|^k + 2|x| + 1$, so we are still fine.)

EDIT 2: Thinking about it some more, the verifier function is a relation $V_C \subseteq \{0, 1\}^\ast \times \{0, 1\}^\ast$ (satisfying the conditions that make it a function). The set $\{0, 1\}^\ast \times \{0, 1\}^\ast$ can be encoded as the subset $C_{\{0, 1\}^\ast \times \{0, 1\}^\ast} = \{1^{|x|}0xy \mid x, y \in \{0, 1\}^\ast\}$, and the indicator function $1_{C_{\{0, 1\}^\ast \times \{0, 1\}^\ast}} : \{0, 1\}^\ast \to \{0, 1\}$ computes the output in linear time. (It exactly includes all the strings of the form $1^n0z$, with $n \geq 0$, and $|z| \geq n$.) A Turing machine can extract $x$ and $y$ from the valid strings belonging to $C_{\{0, 1\}^\ast \times \{0, 1\}^\ast}$ in polynomial time, and follow that with whatever (polynomial) procedure that computes the verifier function. Anyways, the $\mathcal{NP}$ class can be defined building on a definition of the $\mathcal{P}$ class that only involves $\{0, 1\}^\ast \to \{0, 1\}$ functions.

Answer 1

I think you are right that the author's phrasing doesn't seem to immediately suggest a correct formalization of equivalence, but the idea is correct. I think the easiest formalization is the following.

Given $f: \{0,1\}^* \to \{0,1\}^*$, define:

• $\bar{f}: \{0,1\}^* \times \mathbb{N} \to \{0,1\}$ to be $\bar{f}(x,j) = 1$ iff $|f(x)| \leq j$. (Here $|\cdot|$ is string length.)
• $\hat{f}: \{0,1\}^* \times \mathbb{N} \to \{0,1\}$ to be $\hat{f}(x,j) = f(x)_j$, i.e. the $j$th bit of $f(x)$. If $j$ is larger than $|f(x)|$, the output of $\hat{f}(x,j)$ can be, let's say, always $0$.

Now I will leave it as an exercise to prove that if $f$ is computable in polynomial time, then $\bar{f}, \hat{f}$ are in P; and if $\bar{f}, \hat{f}$ are in P, then $f$ is computable in polynomial time. You do need the idea you mentioned, that $|f(x)| \leq |x|^c$ for some $c$.

Answer 2

Since the article seems to be an effort at popularization of science, it probably made sense to the author to not discuss the details of that point.

It seems analogous to defining uniform continuity of a function $f$ and then writing,

Sometimes we will abuse notation and consider continuity at a point instead. After all, a function is determined by its behavior on small intervals $(x-\epsilon,x+\epsilon)$.

It's good if that raises some eyebrows (like the Wigderson passage did for you), but the author didn't write anything that was actually false.