Exercise 113. ▶ [30] [30] Prove that the digital tomography problem is NP-complete, even if the marginal sums $r$, $c$, $a$, $b$ are binary: Show that an efficient algorithm to decide whether or not an $n \times n$ pixel image $(x_{ij})$ exists, having given $0$-$1$ values of $r_i = \sum_j x_{ij}$, $c_j = \sum_i x_{ij}$, $a_d = \sum_{i+j \equiv d} x_{ij}$, $b_d = \sum_{i-j \equiv d} x_{ij}$, could be used to solve the binary tensor contingency problem of exercise 21(c).

Verified: no
Solve time: 2m42s

Setup

The binary tensor contingency problem of exercise 7.2.2.1-212(a) asks whether there exists a binary tensor $(x_{ijk})$, $1\leq i,j,k\leq n$, having prescribed binary marginals

$$ r_{ij}=\sum_k x_{ijk},\qquad c_{jk}=\sum_i x_{ijk},\qquad p_{ik}=\sum_j x_{ijk}. $$

We reduce this problem to digital tomography. The input to the hypothetical tomography algorithm is an $N\times N$ image $(y_{uv})$ together with binary marginal sums

$$ r'u=\sum_v y{uv},\qquad c'v=\sum_u y{uv}, $$

and diagonal sums

$$ a_d=\sum_{u+v=d}y_{uv},\qquad b_d=\sum_{u-v=d}y_{uv}. $$

The goal is to construct these data so that a valid tomographic image exists if and only if the given tensor contingency instance has a solution.

Solution

Choose

$$ M=2n^2. $$

For every triple $(i,j,k)$, create one possible black pixel at coordinates

$$ u=(i-1)M+j, $$

and

$$ v=B-(i-1)M-nk, $$

where

$$ B=(n-1)M+n^2+n+1. $$

Let

$$ y_{uv}=x_{ijk} $$

for these coordinates, and let every other pixel be fixed to $0$.

The row coordinate $u$ uniquely identifies the pair $(i,j)$, because

$$ u=(i-1)M+j $$

with $1\leq j\leq n$ and $M>n$. Therefore the row sum of row $u$ is

$$ \sum_v y_{uv}

\sum_k x_{ijk}

r_{ij}. $$

The column coordinate $v$ uniquely identifies the pair $(i,k)$, because the values

$$ B-(i-1)M-nk $$

are separated into disjoint blocks as $i$ varies, and within each block the value of $k$ is recovered from the multiple of $n$. Hence the column sum of column $v$ is

$$ \sum_u y_{uv}

\sum_j x_{ijk}

p_{ik}. $$

Thus the row and column marginals of the constructed tomography instance are precisely the binary marginals $r_{ij}$ and $p_{ik}$.

The positive diagonal coordinate satisfies

$$ u+v

(i-1)M+j+B-(i-1)M-nk

B+j-nk. $$

Because

$$ 1\leq j\leq n,\qquad 1\leq k\leq n, $$

the values $j-nk$ are all distinct. Indeed, if

$$ j_1-nk_1=j_2-nk_2, $$

then

$$ j_1-j_2=n(k_1-k_2). $$

The left side has absolute value less than $n$, so it must be zero, giving

$$ j_1=j_2,\qquad k_1=k_2. $$

Therefore each positive diagonal corresponds to exactly one pair $(j,k)$. Its sum is

$$ a_{B+j-nk}

\sum_i x_{ijk}

c_{jk}. $$

Hence the diagonal marginals $a_d$ are binary.

It remains to verify the other diagonal family. We have

$$ u-v

2(i-1)M+j+nk-B. $$

For fixed $i$, the value

$$ j+nk $$

determines $(j,k)$ uniquely, because if

$$ j_1+nk_1=j_2+nk_2, $$

then

$$ j_1-j_2=n(k_2-k_1). $$

Again the left side has absolute value less than $n$, so

$$ j_1=j_2,\qquad k_1=k_2. $$

For different values of $i$, the possible values of

$$ 2(i-1)M+j+nk $$

lie in disjoint intervals, since changing $i$ changes the first term by

$$ 2M=4n^2, $$

whereas the total variation of $j+nk$ is less than

$$ n^2+n<4n^2. $$

Consequently every difference diagonal contains at most one constructed pixel. Therefore every $b_d$ is either $0$ or $1$, so the remaining tomographic marginals are binary.

The construction is polynomial in $n$, because the largest coordinate is

$$ O(n^3). $$

Suppose the tensor contingency instance has a solution $(x_{ijk})$. The construction above produces a tomographic image with exactly the required binary marginals.

Conversely, suppose the constructed tomographic instance has a solution $(y_{uv})$. The row and column constraints force all nonzero pixels to occupy only the coordinates corresponding to triples $(i,j,k)$, because every other row or column has required sum $0$. Define

$$ x_{ijk}=y_{(i-1)M+j,;B-(i-1)M-nk}. $$

The row, column, and diagonal constraints then give

$$ \sum_k x_{ijk}=r_{ij}, $$

$$ \sum_j x_{ijk}=p_{ik}, $$

and

$$ \sum_i x_{ijk}=c_{jk}. $$

Thus $(x_{ijk})$ is a solution of the binary tensor contingency problem.

Therefore an efficient algorithm for deciding the digital tomography problem with binary marginal sums would give an efficient algorithm for the binary tensor contingency problem. Since the latter is NP-complete by exercise 7.2.2.1-212(a), digital tomography with binary $r,c,a,b$ is NP-complete.

Verification

The three tensor marginals appear exactly once:

$$ r_{ij} $$

is represented by rows indexed by $(i,j)$,

$$ p_{ik} $$

is represented by columns indexed by $(i,k)$, and

$$ c_{jk} $$

is represented by the $u+v$ diagonals.

The choice

$$ M=2n^2 $$

separates different values of $i$ in the $u-v$ diagonals, while the mixed-radix expression