0
$\begingroup$

I just started learning about NP-Complete problems and one of the first examples they give is Set Cover:

Given a set $U$ of $n$ elements, a collection $S_1, \ldots, S_m$ of subsets of $U$, and a number $k$, does there exist a collection of at least $k$ of these sets with the property that not two of them intersect?

This is I'm sure a very basic question, but I was wondering whether the amount of space in $n$ the input takes up matters at all in the formulation of runtime. This is the first example of an algorithm I've seen where the input itself takes up space exponential in $n$ since of course there are $2^n$ possible subsets of $U$. Thus, it seems that possibly the time needed to allocate the space necessary to even "handle" the input prevents there from being a polynomial time algorithm.

Or rather, do we just assume that the input magically appears in our hands already allocated before we start keeping track of algorithm runtime? And as a side question, can we choose what data structure it is given to us in? This seems more natural to me, but I wanted to make sure. I know, for example, that the time needed to allocate an output (or allocate anything in between) does matter.

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ Your program doesn't have to read all possible 2^n subsets of U; just the ones provided as input. The input for this problem is a set of size n, m sets of size at most n, and one scalar number, which can all be read in time polynomial in m and n; more generally, when talking about a "polynomial time" algorithm, that means polynomial in the input size, and it is surely impossible for the input size to be exponential in itself. $\endgroup$
    – kaya3
    Feb 11, 2020 at 0:03
  • $\begingroup$ @kaya3 Thanks for the response! I still have a question though: With this formulation, wouldn't Set Cover be solvable in polynomial time? All I have to do is iterate over the ${m \choose k}$ subsets of size $k$ of $\{ S_1, \ldots , S_m \}$ and for each collection of subsets check whether no two of them intersect. Checking for intersections in each iteration would I believe take $O(n^2 m^2)$, though that might be off. Regardless it seems to be polynomial. The key fact being we don't need to check collections of size greater than $k$ since if there is a collection of size... $\endgroup$
    – kanso37
    Feb 13, 2020 at 21:05
  • $\begingroup$ @kaya3 ...greater than $k$ where no two $S_i$ intersect then there is a collection of size exactly $k$ where no two intersect. $\endgroup$
    – kanso37
    Feb 13, 2020 at 21:07
  • 1
    $\begingroup$ In general (m choose k) is polynomial in m but exponential in k, and the number of bits needed to describe the input (i.e. m sets of size <= n, plus the scalar k) is not exponential in k. $\endgroup$
    – kaya3
    Feb 13, 2020 at 21:13
  • $\begingroup$ @kaya3 Ah I'm so used to the second part of the choose operation being a constant that I forgot it is actually exponential. Thanks! $\endgroup$
    – kanso37
    Feb 13, 2020 at 21:18

1 Answer 1

Reset to default
2
$\begingroup$

We measure the running time as a function of the length of the input, not as a function of $n$. So, it doesn't matter whether the length of the input is $2^n$ or not.

When we talk about an exponential-time function, we normally mean exponential in the length of the input, not exponential in some other parameter (like $n$).

For your problem, the length of the input could be $2^n$, but it will typically be a lot less than $2^n$, because typically we'll have many fewer sets than that. Either way, it doesn't matter, because we're measuring the running time as a function of the input length.

Typically, the format/representation of the input doesn't affect the running time much; the running time will be identical for any reasonable way to represent or encode the input. So, typically that doesn't matter. In the cases where it does matter, be careful to specify the input representation, or ask if it isn't specified.

Improve this answer
$\endgroup$
0

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.