Santa has a real challenge this year: 187 of his elves were quarantined with Covid 19 during the christmas time, and are now clinically depressed because they missed all of the fun. He wants to give each of them a perfect present, and since they have always envied Santa for his magical sleigh, his idea is to give each of them his own toy sleigh.

Now in the shed, he has a set P of n pieces that will clearly be sufficient to build the sleighs, each of which is available in large amounts. The pieces are such that you will never need more than copy of any p P for the same sleigh. Santa, as an expert, knows what a good sleigh needs: For example, they might each need a front light, and

there might be different ones (p1, . . . , pl) in P , so you must use p1 or . . . or pl. Also, it is important for everything to look great, so he is planning to use at least one red part in each gift and one green one. Actually, Santa has a long list of all kinds of different constraints on the sleigh assembly, which he is writing down similarly as above. As the new intern, Santa is calling you into his office and while you are eating a nice sugar cane, he tasks you with the following: Tomorrow, it is your job to write and run a polynomial-time algorithm that gets as input a formal depiction of Santas constraints, and outputs all 187 different sets of parts for the sleighs (if possible, otherwise return no). Santa promises the assembly will be done by more experienced workers - all you have to take care of is that no two sleighs are exactly the same, so the gifts still feel special enough.

Despite the sugar cane, the assignment leaves a bitter taste in your mouth. However, not wanting to ruin your own christmas, you dont protest right away: that would look just lazy. Come up with a mathematical proof that in gen- eral, this problem is clearly a hard one and might not be solvable for you in a day.

Santa has a real challenge this year: 187 of his elves were quarantined with Covid 19 during the christmas time, and are now clinically depressed because they missed all of the fun. He wants to give each of them a perfect present, and since they have always envied Santa for his magical sleigh, his idea is to give each of them his own toy sleigh. Now in the shed, he has a set P of n pieces that will clearly be sufficient to build the sleighs, each of which is available in large amounts. The pieces are such that you will never need more than copy of any p E P for the same sleigh. Santa, as an expert, knows what a good sleigh needs: For example, they might each need a front light, and there might be different ones (P1, ... , Pl) in P, so you must use p or ... or p. Also, it is important for everything to look great, so he is planning to use at least one red part in each gift and one green one. Actually, Santa has a long list of all kinds of different constraints on the sleigh assembly, which he is writing down similarly as above. As the new intern, Santa is calling you into his office and while you are eating a nice sugar cane, he tasks you with the following: Tomorrow, it is your job to write and run polynomial-time algorithm that gets as input a formal depiction of Santa's constraints, and outputs all 187 different sets of parts for the sleighs (if possible, otherwise return 'no'). Santa promises the assembly will be done by more experienced workers - all you have to take care of is that no two sleighs are exactly the same, so the gifts still feel special enough. Despite the sugar cane, the assignment leaves a bitter taste in your mouth. However, not wanting to ruin your own christmas, you don't protest right away: that would look just lazy. Come up with a mathematical proof that in gen- eral, this problem is clearly a hard one and might not be solvable for you in a day