Author |
Topic: Quiz Team Scheduling (Read 1916 times) |
|
william wu
wu::riddles Administrator
Gender: 
Posts: 1291
|
 |
Quiz Team Scheduling
« on: May 21st, 2003, 4:25pm » |
 Quote  Modify
|
Consider the following problem, called Quiz Team Scheduling (QTS). You are given a set of N college students, each of which has expertise in certain academic subjects (e.g., Entomology, Cinematography, Biology, etc.). There are a total of S possible subjects. Knowing what each student is good at, you want to partition the set of students into two teams (not necessarily the same size) such that each team spans all N subjects. In other words, for any given subject, there exists at least one guy in each team which knows that subject.
So for example, the following is a YES-instance of QTS; X marks mean the student in that row knows the subject in that column:
| Entomology | Furballogy | Geology | Histology | | Alice | X | | | X | | Bob | | X | X | X | | Carol | X | X | | | | Dick | | X | X | |
Simply choose Alice and Dick for one team, and Bob and Carol for the other team.
It's easy to show that the QTS problem is in NP. By reduction from 3-SAT (yes 3-SAT specifically), show that the QTS problem is also NP-hard, and thus NP-complete.
Notes for the NP-clueless:
1. 3-SAT = { phi | phi is a satisfiable boolean formula in 3-CNF (conjunctive normal form) }. So it's a logic formula structured like the following example:
(x1 OR ~x2 OR x3) AND (x1 OR x5 OR ~x5) AND ...
The tilde symbol "~" denotes the negation operator. We call the parenthesized groups "clauses", and terms like x1 are called "literals." The key thing to realize is that at least one literal in each clause must be true, and every clause must be satisfied.
2. Reduction review: Roughly speaking, when we do reductions, we are trying to figure out how two problems are equivalent to each other. This problem asks you to show how finding a satisfying assignment to a 3-SAT formula is equivalent to finding a satisfying partition of college kids to span all subjects. 3-SAT is a canonical NP-complete problem, which means it's a hard problem ... we don't know any polynomial time algorithms which can solve it. Now suppose we had a black box that could solve the QTS problem. If we could use this black box to solve 3-SAT, then that would show that QTS is at least as hard of a problem as 3-SAT. Our goal is to show that this can be done.
Given a 3-SAT formula phi, design a corresponding QTS scenario such that phi has a solution IF AND ONLY IF the QTS scenario has a solution. Spelled out:
- If phi has a satisfying assignment, then your QTS scenario has a satisfying partition, and
- If phi does not have a satisfying assignment, then your QTS scenario has no satisfying partition
You will have to figure out what aspects of the logic formula that the students and subjects will somehow capture.
3. What do we mean by the terminology "YES-instance of QTS?" Computer science theoreticians sometimes like to think of the solution space to problems as languages, like the languages of regular expressions. A language is a set of strings of characters over some finite alphabet. Given an arbitrary string, we want to decide if it belongs in a certain language. So any string is either in our out -- it's either YES or NO. A QTS scenario can be encoded up into a string of characters (the table drawn above was done in ASCII). So that was a YES-instance, because it could be partitioned into two teams that each span all subjects.
Problem Source: UC Berkeley CS172 (Computability and Complexity Theory) Final Exam, Spring 2003
|
| « Last Edit: May 21st, 2003, 4:59pm by william wu » |
 IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
Papa Homer
Guest
|
A simpler way to show that a problem is in NP is to swow that a result can be verified in P. Now, to show NP-hardness you do need to reductions.
|
|
IP Logged |
|
|
|
Rezyk
Junior Member
Gender:
Posts: 85
|
|
Re: Quiz Team Scheduling
« Reply #2 on: Oct 20th, 2003, 11:47am » |
Quote Modify
|
For the ith student, create a new boolean literal gi (represents the truth value of "the ith student goes in the first team").
For each subject j, create a clause fj made from the disjunction of the gi's of the students good at that subject (represents the truth value of "the first team spans subject j"). Also create a clause sj out of the disjunction of all their negations (represents the truth value of "the second team spans subject j").
The condition that "each team span all subjects" is equivalent to the conjunction of all fj's and all gj's, which is in CNF with each of the 2S clauses having up to N terms.
We then reduce this form to 3-CNF. While there is a clause with more than 3 literals, repeat this: {
Create a new literal z.
Replace 2 terms x and y in the offending clause with z.
Add the clause "(~z OR x OR y)"
}
Given the size of the original clauses, this should need to be done O(SN) times at most.
|
|
IP Logged |
|
|
|
Dudidu
Full Member
Posts: 227
|
|
Re: Quiz Team Scheduling
« Reply #3 on: Oct 26th, 2003, 3:22am » |
Quote Modify
|
on Oct 20th, 2003, 11:47am, Rezyk wrote:
Rezyk hi,
I've been looking at your solution and I don't understand what you're trying to prove  .
If you're trying to prove that QTS problem is in NP-hard, I think you are wrong (in your solution, you're trying to show that 3-SAT is harder then QTS !!!).
For my opinion (and knowledge), if you want to show that QTS is NP-hard you need to show that given a 3-SAT formula [phi], you can design a corresponding QTS scenario such that [phi] has a solution IFF the QTS scenario has a solution (and this is the oposite direction of your reduction).
Waiting for your reply... 
|
| « Last Edit: Oct 26th, 2003, 3:22am by Dudidu » |
IP Logged |
|
|
|
Rezyk
Junior Member
Gender:
Posts: 85
|
|
Re: Quiz Team Scheduling
« Reply #4 on: Oct 26th, 2003, 7:36am » |
Quote Modify
|
Doh! How careless of me...!  You're absolutely right.
What I meant to say was..
From 3-SAT, for each clause cj, create a subject Cj. For each literal xi, create students Xi and NOTXi and subject Li. Create an additional student EINSTEIN.
The subjects Xi knows are exactly: Cj for every clause cj which xi appears in (without a negation), and Li.
The subjects NOTXi knows are exactly: Cj for every clause cj which ~xi appears in, and Li.
The subjects EINSTEIN knows are exactly: all Cj's.
Any satisfying assignment to this QTS must have Xi and NOTXi on different teams (because they are the only ones who know Li), and corresponds to a satisfying assignment for 3-SAT by taking: xi is true iff (Xi is on one team while EINSTEIN and NOTXi are on the other), otherwise (NOTXi is on one team while EINSTEIN and Xi are on the other). Each cj's satisfaction can be seen to correspond with both teams knowing Cj.
My thought process in coming up with this solution:
"...darn you, Dididu...  Okay, since a 3-SAT clause and QTS subject both test for a at-least-one-of-this-list-must-hold quality, they probably correspond to each other and the literals would correspond to students. So create the Xi's, XNOTi's, and Cj's, and tie student-knowing-subject to literal-in-clause. Hmm...what important qualities of 3-SAT are left out by this? Well, the anticorrelation between xi and ~xi is definitely needed to keep everything from being trivial, but that can be easily enforced by an additional subject Li that forces them to be on opposing teams, so only one of each gets to be on team 1 (I was thinking that all students on team 1 would correspond to true in the final assignment). That should be enough to emulate all the inherent difficulty of 3-SAT...now to check that the problems are equivalent. Shoot, I didn't account for team 2's subject satisfication properly...there might be a 3-SAT clause which needs to end up as (true V true V true), putting all 3 students on team 1, making team 2 lose out and failing QTS. Is there a way to let team 2 easily satisfy the Cj's? A tailor-made uber-student is the straightforward way...does that interfere with team 1 difficulty? Nope, seems to work; I guess he would be what distinguishes team 1 from team 2, which is also something I needed. Okay...everything was pretty simple so I shouldn't need to explicitly show that the reduction is poly-time. This answer is kind of stale though...maybe I should add a whole my-thought-process section to it or something..."
|
| « Last Edit: Oct 26th, 2003, 8:50am by Rezyk » |
IP Logged |
|
|
|
Dudidu
Full Member
Posts: 227
|
|
Re: Quiz Team Scheduling
« Reply #5 on: Oct 27th, 2003, 4:28am » |
Quote Modify
|
Rezyk, now its seems to be right  !
This, of course, proves that QTS is NP-hard. To show that QTS is in NPC we only need to show that the verification of a solution to QTS is in P (which is easy, since given two teams , the verification algorithm will check that each of the "team's knowledge" spans all the subjects).
p.s. --> I found your thought process section very intresting (well done  )
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print
Remove