To show that the Pivot Scheduling problem is NP-hard, we can use a reduction from the 3-SAT problem, which is a well-known NP-hard problem.
The 3-SAT problem is defined as follows: given a boolean formula in conjunctive normal form (CNF) with variables x1, x2, ..., xn and clauses c1, c2, ..., cm, where each clause is a disjunction of exactly three literals (i.e., a variable or its negation), the task is to determine whether there exists a truth assignment to the variables that satisfies all clauses.
We can reduce the 3-SAT problem to the Pivot Scheduling problem as follows:
1. For each variable xi, create two jobs xi and yi.
2. For each clause cj, create a job zj.
3. For each literal l in clause cj, create an ordering constraint {l, zj} if l is a positive literal (i.e., a variable) or {l', zj} if l is a negated literal (i.e., a negated variable).
4. For each variable xi, create an ordering constraint {xi, yi}.
5. The before set V1 consists of all xi and yi jobs, and the after set V2 consists of all zj jobs.
It is easy to see that this reduction can be done in polynomial time.
Now, we will prove that there is a satisfying truth assignment for the 3-SAT formula if and only if there is a valid partition of V into V1 and V2 for the Pivot Scheduling problem.
If there is a satisfying truth assignment for the 3-SAT formula, we can partition V into V1 and V2 as follows:
* For each xi such that xi is true in the truth assignment, include xi in V1 and yi in V2.
* For each xi such that xi is false in the truth assignment, include yi in V1 and xi in V2.
* For each zj, include zj in V2.
This partition satisfies the before constraints because each pair xi, yi has one element in V1 and one element in V2. It also satisfies the after constraints because for each clause cj, at least one literal in cj is true, so the corresponding job is in V1, and the job zj is in V2.
Conversely, if there is a valid partition of V into V1 and V2 for the Pivot Scheduling problem, we can construct a truth assignment for the 3-SAT formula as follows:
* For each xi such that xi is in V1, set xi to be true.
* For each xi such that yi is in V1, set xi to be false.
It is easy to see that this truth assignment satisfies all clauses, because for each clause cj, at least one literal in cj is in V1, so it is set to be true.
Therefore, the Pivot Scheduling problem is NP-hard.
