<p>This is a possible reduction from 3-partition which is strongly NP-complete.</p>

<p>Given a set $A = \{a_1,a_2,...,a_{3m}\}$ of $3m$ positibe integers, and a target sum $B$.</p>

<p>The basic idea is simple: if we found a read sequence like $Rx1\; Rx2\; Rx1$, even if the last write of $x$ before the sequence was a $Wx2$, the first $Rx1$ forces to "use" another $Wx2$ to satisfy the $Rx2$ in the middle.</p>

<p>We represent each $a_i$ with a <em>unary</em> chain $P_{a_i}$ made of $a_i+2$ write operations: the first operation is a $Wx2$ (green boxes in the figure), followed by $a_i$ write operations $Wy2$ (gray boxes), followed by a single $Wz2$ (blue boxes) write operation.</p>

<p>We add three <em>auxiliary</em> chains $P_{c_1}, P_{c_2}, P_{c_3}$. $P_{c_1}$ made with $4m$ write operations $Wx1$, $P_{c_2}$ made with $B \cdot m = \sum_{i=1}^{3m} a_i$ write operations $Wy1$,  $P_{c_3}$ made with $4m$ write operations $Wz1$.</p>

<p>Now we build the chain $P_0$ made only with read operations in the following way:
concatenate $m$ <em>slot subsequences</em>; each slot subsequence is made with:</p>

<ul>
<li><p>a leading <em>open sequence</em> $Rx1\; Rx2\;  Rx1\;  Rx2\;  Rx1\;  Rx2\;  Rx1$, that forces to <em>pop</em> three operations $Wx2$ from three distinct $P_{a_i}$ and <em>open</em> those chains;</p></li>
<li><p>followed by a <em>sum sequence</em> $Ry1\; Ry2$ repeated $B$ times, that forces to pop $B$ operations $Ry2$ from the chains that are currently open;</p></li>
<li><p>followed by a trailing <em>close sequence</em> $Rz1\; Rz2\;  Rz1\;  Rz2\;  Rz1\;  Rz2\;  Rz1$, that forces to <em>pop</em> three operations $Wz2$ from the end of the chains that are currently opened.</p></li>
</ul>

<p>Note that if a chain is opened and some $Wy2$ are still there and in order to complete the current close sequence  we pop them  (without a corresponding $Ry2$) to reach the final $Wz2$, in one of the next slot subsequences there will be not enough $Wy2$ to reach the close sequence. And if we are in the middle of a sum sequence and we need a $Wy2$ but we've already reached the end of all the currently opened $a_i$ chains, we cannot open another chain to recover a $Wy2$ to complete the sum sequence, otherwise in one of the next slot subsequences there will be not enough $Wx2$ to complete an open sequence.</p>

<p>The figure represents the instance: $A = \{ 3,3,2,2,2,2 \}$, $m=2$, $B=7$ (note that every $a_i$ should be between $B/4$ and $B/2$ to force exactly three elements in each <em>slot sequence</em>) </p>

<p><img src="https://i.sstatic.net/z6giR.png" alt="enter image description here"></p>

<p>NOTE: as noted in the comments, the trailing $Rx1$ (resp. $Rz1$) of the open (resp. close) sequences are unuseful and they can be removed (and $P_{c1}, P_{c3}$ shortened to $3m$ elements).</p>

CC BY-SA 3.0
2013-09-28T02:10:02.443Z
Thanks a lot. I need time to understand it before accepting it. Also, I need more comments from peer reviewers.
hengxin
CC BY-SA 3.0
2013-09-28T08:10:43.620Z
@hengxin: ok! I'll check it again later, too (to be honest I didn't think about it, too much :-)
Marzio De Biasi
CC BY-SA 3.0
2013-10-02T07:25:04.690Z
I got the basic idea of your smart reduction. I tend to believe that it is right. Three questions here: (1) What does the last $Rx1$ do in the read sequence pattern $Rx1, Rx2, Rx1$ (also in open sequence and close sequence)? I think $Rx1, Rx2$ is enough to force to use another $Wx2$ to satisfy the $Rx2$. (2) Does your reduction imply that the scheduling problem is NP-hard even when only three variables are used and $P_0$ is read-only? (3) You said that ``$P_{c2}$ is made with $3m$ write operations $Wy1$''. Is it $B \cdot m = \sum A_i$ instead of $3m$ (slip of the pen)? Thanks.
hengxin
CC BY-SA 3.0
2013-10-02T08:42:09.540Z
@hengxin: (1) yes it is unuseful: but I realized it after drawing the figure so I leaved it :) (2) yes (it is also in NP so it is NP-complete) (3) yes it is $B \cdot m = \sum_{i=1}^{3m} a_i$
Marzio De Biasi
CC BY-SA 3.0
2013-10-02T10:55:03.113Z
@hengxin: perhaps you can replace Wy1,Wy2,Ry1,Ry2 and Wz1,Wz2,Rz1,Rz2 with Wx3,Wx4,Rx3,Rx4 and Wx5,Wx6,Rx5,Rx6 ... so a single variable is enough ... I'll think about it.
Marzio De Biasi
CC BY-SA 3.0
2013-10-03T02:10:10.600Z
ok. I'll think about it and leave the post open for a few more days before accepting.
hengxin
CC BY-SA 3.0
2013-10-03T09:47:07.427Z
@hengxin: ok! if the result is new, perhaps it might be worth publishing it in a joint paper (or at least submit it to arXiv)???
Marzio De Biasi
CC BY-SA 3.0
2013-10-04T01:46:26.617Z
ok. Let's talk about the paper thing. Could you give me your email or just send your suggestions to hengxin0912@gmail.com. I also have some information for you.
hengxin
CC BY-SA 3.0
2013-09-27T23:19:52.163Z
2013-10-02T08:52:35.513Z
2013-10-02T08:52:35.513Z
Marzio De Biasi
<p>The scheduling problem (arising from distributed computing) is defined as a decision problem as follows:</p>

<p><strong>Instance:</strong></p>

<blockquote>
  <p>A <em>trace</em> is comprised of $n$ processes histories (denoted $p_0, p_1, \ldots, p_{n-1}$), each of which consisting of a finite sequence of Read and Write operations on <em>multiple shared variables</em> in program order.</p>
  
  <p>An important restriction here is that <em>all the Read operations are on the process</em> $p_0$.</p>
</blockquote>

<p><strong>Example:</strong></p>

<blockquote>
  <p><img src="https://i.sstatic.net/3tHYW.png" alt="&quot;simple trace&quot;"> The above figure gives a trace example. Here, $W$ is for Write operation, and $R$ is for Read operation. $Wx1$ means updating the shared variable $x$ to 1. $Ry3$ means reading the shared variable $y$ and returning 3.</p>
</blockquote>

<p><strong>Problem:</strong></p>

<blockquote>
  <p>Is there some schedule (i.e., a sequence) of all the operations such that:</p>
  
  <ul>
  <li>the program order between operations is maintained;</li>
  <li>in the schedule, each Read should read the value from the latest preceding Write on the same variable.   </li>
  </ul>
</blockquote>

<p><strong>Example (Cont.):</strong></p>

<blockquote>
  <p>For example, the trace in the above figure can be scheduled as follows:
  $$Wx1(p_1), Wx1(p_0), Rx1, Wx2(p_1), Wy3, Ry3, Wx2(p_0), Wx1(p_3), Rx1.$$</p>
</blockquote>

<p><strong>Now, I want to study the complexity issue of this decision problem. Specifically, is this decision problem NP-hard?</strong></p>

CC BY-SA 3.0
2013-09-27T07:12:20.420Z
Some clarifications: it is not clear if the read operations of the schedule must occur *exactly* after a write on the same variable. In your example is Wx1(p0),Wx1(p1),Wx2(p1),Rx1,... a valid scheduling? Furthermore the trace itself seems to induce a valid scheduling (scan right-to-left, when you find a read operation put the corresponding write operation just before it if it exists, otherwise reject).
Marzio De Biasi
CC BY-SA 3.0
2013-09-27T07:39:00.560Z
$Wx1(p_0),Wx1(p_1),Wx2(p_1),Rx1, \ldots$ is not valid, because $x$ has been updated to 2 by $p_1$ and $Rx1$ is not possible to return the stale value 1. However, it does not mean that the read operations of the schedule must occur *exactly* after a write on the same variable. A write on a different variable may be between them. In addition, there may be many "writes" updating the same variable to the same value, so your "scan" algorithm encounters **non-determinism**. Actually, I think the *non-determinism* may be the *hardness* of the scheduling problem. Thanks.
hengxin
<cc.complexity-theory><np-hardness><dc.distributed-comp><scheduling>
Is This Scheduling Problem NP-Hard?
hengxin
# Is This Scheduling Problem NP-Hard?

(Asked by: username_0 on 2013-09-27)

The scheduling problem (arising from distributed computing) is defined as a decision problem as follows:

**Instance:**

> A *trace* is comprised of $n$ processes histories (denoted $p\_0, p\_1, \ldots, p\_{n-1}$), each of which consisting of a finite sequence of Read and Write operations on *multiple shared variables* in program order.
>
> An important restriction here is that *all the Read operations are on the process* $p\_0$.

**Example:**

> ![](https://i.sstatic.net/3tHYW.png) The above figure gives a trace example. Here, $W$ is for Write operation, and $R$ is for Read operation. $Wx1$ means updating the shared variable $x$ to 1. $Ry3$ means reading the shared variable $y$ and returning 3.

**Problem:**

> Is there some schedule (i.e., a sequence) of all the operations such that:
>
> * the program order between operations is maintained;
> * in the schedule, each Read should read the value from the latest preceding Write on the same variable.

**Example (Cont.):**

> For example, the trace in the above figure can be scheduled as follows:
> $$Wx1(p\_1), Wx1(p\_0), Rx1, Wx2(p\_1), Wy3, Ry3, Wx2(p\_0), Wx1(p\_3), Rx1.$$

**Now, I want to study the complexity issue of this decision problem. Specifically, is this decision problem NP-hard?**

**Tags:** cc.complexity-theory, np-hardness, dc.distributed-comp, scheduling

> **Comments:**
> **username_1**: Some clarifications: it is not clear if the read operations of the schedule must occur *exactly* after a write on the same variable. In your example is Wx1(p0),Wx1(p1),Wx2(p1),Rx1,... a valid scheduling? Furthermore the trace itself seems to induce a valid scheduling (scan right-to-left, when you find a read operation put the corresponding write operation just before it if it exists, otherwise reject).  
> **username_0**: $Wx1(p_0),Wx1(p_1),Wx2(p_1),Rx1, \ldots$ is not valid, because $x$ has been updated to 2 by $p_1$ and $Rx1$ is not possible to return the stale value 1. However, it does not mean that the read operations of the schedule must occur *exactly* after a write on the same variable. A write on a different variable may be between them. In addition, there may be many "writes" updating the same variable to the same value, so your "scan" algorithm encounters **non-determinism**. Actually, I think the *non-determinism* may be the *hardness* of the scheduling problem. Thanks.  

---

## 1 answers

### Answer by username_1 on 2013-09-27. Score: 4 | Accepted answer

This is a possible reduction from 3-partition which is strongly NP-complete.

Given a set $A = \{a\_1,a\_2,...,a\_{3m}\}$ of $3m$ positibe integers, and a target sum $B$.

The basic idea is simple: if we found a read sequence like $Rx1\; Rx2\; Rx1$, even if the last write of $x$ before the sequence was a $Wx2$, the first $Rx1$ forces to "use" another $Wx2$ to satisfy the $Rx2$ in the middle.

We represent each $a\_i$ with a *unary* chain $P\_{a\_i}$ made of $a\_i+2$ write operations: the first operation is a $Wx2$ (green boxes in the figure), followed by $a\_i$ write operations $Wy2$ (gray boxes), followed by a single $Wz2$ (blue boxes) write operation.

We add three *auxiliary* chains $P\_{c\_1}, P\_{c\_2}, P\_{c\_3}$. $P\_{c\_1}$ made with $4m$ write operations $Wx1$, $P\_{c\_2}$ made with $B \cdot m = \sum\_{i=1}^{3m} a\_i$ write operations $Wy1$, $P\_{c\_3}$ made with $4m$ write operations $Wz1$.

Now we build the chain $P\_0$ made only with read operations in the following way:
concatenate $m$ *slot subsequences*; each slot subsequence is made with:

* a leading *open sequence* $Rx1\; Rx2\; Rx1\; Rx2\; Rx1\; Rx2\; Rx1$, that forces to *pop* three operations $Wx2$ from three distinct $P\_{a\_i}$ and *open* those chains;
* followed by a *sum sequence* $Ry1\; Ry2$ repeated $B$ times, that forces to pop $B$ operations $Ry2$ from the chains that are currently open;
* followed by a trailing *close sequence* $Rz1\; Rz2\; Rz1\; Rz2\; Rz1\; Rz2\; Rz1$, that forces to *pop* three operations $Wz2$ from the end of the chains that are currently opened.

Note that if a chain is opened and some $Wy2$ are still there and in order to complete the current close sequence we pop them (without a corresponding $Ry2$) to reach the final $Wz2$, in one of the next slot subsequences there will be not enough $Wy2$ to reach the close sequence. And if we are in the middle of a sum sequence and we need a $Wy2$ but we've already reached the end of all the currently opened $a\_i$ chains, we cannot open another chain to recover a $Wy2$ to complete the sum sequence, otherwise in one of the next slot subsequences there will be not enough $Wx2$ to complete an open sequence.

The figure represents the instance: $A = \{ 3,3,2,2,2,2 \}$, $m=2$, $B=7$ (note that every $a\_i$ should be between $B/4$ and $B/2$ to force exactly three elements in each *slot sequence*)

![enter image description here](https://i.sstatic.net/z6giR.png)

NOTE: as noted in the comments, the trailing $Rx1$ (resp. $Rz1$) of the open (resp. close) sequences are unuseful and they can be removed (and $P\_{c1}, P\_{c3}$ shortened to $3m$ elements).

> **Comments:**
> **username_0**: Thanks a lot. I need time to understand it before accepting it. Also, I need more comments from peer reviewers.  
> **username_1**: @username_0: ok! I'll check it again later, too (to be honest I didn't think about it, too much :-)  
> **username_0**: I got the basic idea of your smart reduction. I tend to believe that it is right. Three questions here: (1) What does the last $Rx1$ do in the read sequence pattern $Rx1, Rx2, Rx1$ (also in open sequence and close sequence)? I think $Rx1, Rx2$ is enough to force to use another $Wx2$ to satisfy the $Rx2$. (2) Does your reduction imply that the scheduling problem is NP-hard even when only three variables are used and $P_0$ is read-only? (3) You said that ``$P_{c2}$ is made with $3m$ write operations $Wy1$''. Is it $B \cdot m = \sum A_i$ instead of $3m$ (slip of the pen)? Thanks.  
> **username_1**: @username_0: (1) yes it is unuseful: but I realized it after drawing the figure so I leaved it :) (2) yes (it is also in NP so it is NP-complete) (3) yes it is $B \cdot m = \sum_{i=1}^{3m} a_i$  
> **username_1**: @username_0: perhaps you can replace Wy1,Wy2,Ry1,Ry2 and Wz1,Wz2,Rz1,Rz2 with Wx3,Wx4,Rx3,Rx4 and Wx5,Wx6,Rx5,Rx6 ... so a single variable is enough ... I'll think about it.  
> **username_0**: ok. I'll think about it and leave the post open for a few more days before accepting.  
> **username_1**: @username_0: ok! if the result is new, perhaps it might be worth publishing it in a joint paper (or at least submit it to arXiv)???  
> **username_0**: ok. Let's talk about the paper thing. Could you give me your email or just send your suggestions to username_00912@gmail.com. I also have some information for you.  

---

