Class Scheduling to Boolean satisfiability [Polynomial-time reduction]
I am going to try and first formalize the problem, and then attempt to reduce it to SAT. Define the class scheduling problem as: Input = { S1,S2,….,Sn | Si = {(x_i1, y_i1), (x_i2, y_i2) , … , (x_ik, y_ik) | 0 <= x_ij < y_ij <= M } } Informally: The input is a … Read more