Boolean satisfiability problem
GISDPk is NP-complete when formula_1, even when all intervals have the same length. This can be shown by a reduction from the following version of the Boolean satisfiability problem: