Author |
Topic: Finding if a set of subsets contains a partition (Read 1631 times) |
|
dudiobugtron
Uberpuzzler
Posts: 735
|
 |
Finding if a set of subsets contains a partition
« on: Jun 5th, 2014, 7:32pm » |
 Quote  Modify
|
Hi! (Apologies if this is not the right place to post this, as it's a straight CS question and not a riddle I know the answer to. It's not homework, and is just for my personal interest.)
Here is the problem:
-----------------------
I have a set N = {1,2,3,...,n}. I also have a set S of subsets of N. (So S is a subset of the powerset of N). I want to know if there is some subset P of S where the elements of P form a partition of N. (ie: each element of N is in exactly 1 element of P.)
eg: N = {1,2,3,4,5}
S = {{1},{1,2},{2,3},{3,5},{1,4},{2,4},{1,4,5}}
P = {{2,3},{1,4,5}} is a partition of N.
Does anyone have a good algorithm for determining this? Is this a known problem? Is it P? NP complete? etc...
|
|
 IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender: 
Posts: 7526
|
|
Re: Finding if a set of subsets contains a partiti
« Reply #1 on: Jun 6th, 2014, 4:42pm » |
Quote Modify
|
The number of subsets of the powerset of N is exponential in N. So could be S.
But maybe there is a solution that is polynomial in the size of S.
|
| « Last Edit: Jun 6th, 2014, 4:42pm by Grimbal » |
IP Logged |
|
|
|
dudiobugtron
Uberpuzzler
Posts: 735
|
|
Re: Finding if a set of subsets contains a partiti
« Reply #2 on: Jun 6th, 2014, 6:48pm » |
Quote Modify
|
on Jun 6th, 2014, 4:42pm, Grimbal wrote:The number of subsets of the powerset of N is exponential in N. So could be S.
But maybe there is a solution that is polynomial in the size of S. |
|
So does that mean there is certainly not a general solution that is polynomial in N? If so, that is really useful to know. 
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Finding if a set of subsets contains a partiti
« Reply #3 on: Jun 7th, 2014, 4:25am » |
Quote Modify
|
Suppose S is the set of all subsets of N that contain 1. There is no way to find that out except by looking at all of S, the size of which is exponential in N (it's 2N-1). So no, there is not a general solution that is polynomial in N.
Unless, perhaps you get some index to S (i.e. information that let's you skip (to) parts of input without having to process it). But even then I'm doubtful.
|
| « Last Edit: Jun 7th, 2014, 4:26am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
dudiobugtron
Uberpuzzler
Posts: 735
|
|
Re: Finding if a set of subsets contains a partiti
« Reply #4 on: Jun 9th, 2014, 12:41pm » |
Quote Modify
|
OK, that makes a lot of sense, thanks!
So I need to restrict myself to subsets S that are themselves polynomial in N, and then find a solution which is polynomial in S.
------------------------------
PS: I think it is cool that adding more items to the subset actually makes it harder to tell if it contains a partition. Naively, you might think that since adding more elements makes it more likely to contain a partition, that it would be easier to tell if it did. But I guess a better way to think about it is that it's harder to tell that it doesn't.
|
| « Last Edit: Jun 9th, 2014, 12:45pm by dudiobugtron » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print