Comment by iNic

This paper looks exclusively at decision problems, i.e. problems where the output is a single bit.

EDIT: This makes sense because if you look at all problems with N outputs then that is just the same as "gluing together" N different decision problems (+ some epsilon of overhead)