# How does the length of the output of a problem inform its complexity?

Consider the decision problem: Subset sum. For an input set of integers, it asks for a Yes/No answer to the question of whether or not we can find a subset of elements of this input that add up to 0. The output for this problem is $$O(1)$$ and simple (e.g. 1/0). This problem is NP-Complete, which as far as I understand is only defined for decision problems.

Now consider a problem associated with Subset sum that asks to output all such subsets that add up to 0. As far as I understand, this is an optimization problem.

Moreover, the output of this problem could grow as $$O(2^N)$$ if $$N$$ is the size of the input array (i.e. the output grows as fast as the cardinality of the power set of the input). If so, what does this say about the complexity or complexity class of this optimization problem?

More generally speaking, does the size of the output of an optimization problem provide a necessary lower bound on the complexity of the optimization or associated decision problems?

No, it's not an optimization problem. It takes at least one step of computation per bit or word of output (depending on the model of computation), so since the output can be $$\Omega(2^N)$$, that means the worst-case running time will be $$\Omega(2^N)$$, no matter what algorithm you use. Thus, the complexity is $$\Omega(2^N)$$.
• Thanks! When you say one step per bit, I'm curious about this. What computational model would that be for? (does it have an actual name?) I ask because I'm used to the CLRS notation which I think the authors call the "RAM model" and which assumes constant-time operations for k-bit-word-sized data (e.g. words can be k=32 bits, or k=64 bits). Would the number of bits per computer word actually change the complexity e.g. in the case you described ("one step of computation per bit, so you the output can be $Ω(2^𝑁)$"?