Choose an integer n and construct the set S with n elements. Then construct a set, s, of subsets of S such that finding the minimum subset of s (that minimises the sum of the orders of all chosen sets of s in that subset) the union of which covers S is computationally intractable on current hardware.
My question is how would one choose n and construct s such that finding a minimum (or to relax it a bit, an approximation to a minimum) set cover is computationally intractable?
I understand the greedy algorithm for set cover, but I don't understand how to explicitly create an intractable instance of this problem.
The greedy algorithm is to, at each iteration, select the member of s which covers the largest number of elements of S not already covered by previously selected members of s. Take the union of all of these selected members of s, until S is covered.
Also, by intractable I mean something like ' even running at 70 million set choices per second the greedy algorithm on such an instance would take 10**(F(n)) years ' where F is polynomial in n, or similar.
Also I don't understand what relevance this would have for anything else, it just occurred to me as interesting to know what the structure of such an intractable instance would look like.