Content deleted Content added
m typo |
Erel Segal (talk | contribs) |
||
Line 41:
=== NP-complete when some groups contain 3 or more intervals ===
GISDPk is NP-complete when <math>k\geq 3</math>,<ref name=NakajimaHakimi>{{Cite journal | doi = 10.1016/0196-6774(82)90030-X| title = Complexity results for scheduling tasks with discrete starting times| year = 1982| last1 = Nakajima | first1 = K. | last2 = Hakimi | first2 = S. L. | journal = Journal of Algorithms| volume = 3| issue = 4| pages = 344}}</ref> even when all intervals have the same length.<ref name=Keil>{{Cite journal | doi = 10.1016/0167-6377(92)90087-j| title = On the complexity of scheduling tasks with discrete starting times| year = 1992| last1 = Mark Keil | first1 = J. | journal = Operations Research Letters| volume = 12| issue = 5| pages = 293–295}}</ref> This can be shown by a reduction from the following version of the [[Boolean satisfiability problem]], which was shown <ref>{{Cite book|last1=Papadimitriou|first1=Christos H.|title=Combinatorial Optimization : Algorithms and Complexity|last2=Steiglitz|first2=Kenneth|date=July 1998|publisher=Dover|isbn=978-0-486-40258-1|author2-link=Kenneth Steiglitz}}</ref> to be [[NP-complete]] likewise to the unrestricted version.
at most three literals and (2) each variable is restricted to appear once or twice positively and once negatively overall in ''C''. Decide whether there is an assignment to variables of ''X'' such that each clause in ''C'' has at least one true literal.▼
▲::Let <math>X = \{x_1, x_2,..., x_p\}</math> be a set of Boolean variables. Let <math>C = \{c_1, c_2,..., c_q\}</math> be a set of clauses over ''X'' such that (1) each clause in ''C'' has at most three literals and (2) each variable is restricted to appear once or twice positively and once negatively overall in ''C''. Decide whether there is an assignment to variables of ''X'' such that each clause in ''C'' has at least one true literal.
Given an instance of this satisfiability problem, construct the following instance of GISDP. All intervals have a length of 3, so it is sufficient to represent each interval by its starting time:
* For every variable <math>x_i</math> (for ''i''=1,...,''p''), create a group with two intervals: one starting at <math>50i-10</math> (representing the assignment <math>x_i=false</math>) and another starting at <math>50i+10</math> (representing the assignment <math>x_i=true</math>).
| |||