1
$\begingroup$

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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

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)$.

Yes, the size of the output is a lower bound on the running time to produce that output.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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^𝑁)$"? $\endgroup$
    – Josh
    Commented Apr 21, 2020 at 14:58
  • $\begingroup$ @Josh, in that model, it would be one step per word of output. $\endgroup$
    – D.W. ♦
    Commented Apr 21, 2020 at 16:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.