Please prove that the following problem is NP-hard.
The problem is called Pivot Scheduling and is defined as follows.
An instance has the form (V, C), where V is a set of jobs that come in pairs and C is a set of ordering constraints. Namely, let x1, ..., n and y1, ..., yn be 2n distinct jobs, where for each 1 <= i <= n, we view the jobs xi and NAME_1 as paired. Denote by
V the set of all jobs, i.e., V = {x1, y1, . .., xn, yn}. Each ordering constraint C /in C is a set
C /subseteq V of three jobs. The task is to partition V into two subsets, a before set V1 and an after set V2, such that the following hold:
1. Before constraints: For each pair xi, NAME_1, we have either xi /in V1 or NAME_1 /in V1.
2. After constraints: For each C /in C, one of the jobs in C must be in V2, i.e., C /cap V2 = /emptyset. Make sure your entire response is wrapped in JSON format.
user