While this submission is a draft, it cannot be used by other submissions.

Proof of `The Complexity of Fair Repetitive Interval Scheduling in the Fairness Parameter` (1st statement)

groundedproofs/Lax117284Proofs/Theorem1_Tractable.lean · lax-117284

What this proof establishes

Assuming the claims on the left, the claim on the right holds — checked by the archive's pipeline. Proof code is not displayed here.

Read the Lean proof on GitHub

Description

The three tractable values of the fairness parameter reduce, as one reduction, to 2-satisfiability. A word that encodes an instance whose parameter is one below its number of days is sent to the formula of Theorem 9. One whose parameter equals its number of days is sent to the conflict clauses of that formula together with a clause asking for every variable to be true: the formula is satisfiable exactly when no two jobs of a day conflict, which is when every client can be served on every day. One whose parameter is zero is sent to a formula with no clause, since a client served on no day is served enough. A word that encodes no instance with one of these parameters is sent to an unsatisfiable formula. The reduction is a word RAM program on the zeros and ones of its input, in the same way as the reduction of Theorem 9, and 2-satisfiability is in polynomial time.