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\}$? 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 &gt; 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.
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$.