Reconstructing polyatomic structures from discrete X-rays:: NP-completeness proof for three atoms

We address a discrete tomography problem that arises in the study of the atomic structure of crystal lattices. A polyatomic structure T can be defined as an integer lattice in dimension D greater than or equal to 2, whose points may be occupied by c distinct types of atoms. To "analyze" T, we conduct E measurements that we call discrete X-rays. A discrete X-ray in direction xi determines the number of atoms of each type on each line parallel to xi. Given l such non-parallel X-rays, we wish to reconstruct T. The complexity of the problem for c = 1 tone atom type) has been completely determined by Gardner ct al. (Technical Report 970.05012, Techn. Univ. Munchen, Fak. f. Math., 1997), who proved that the problem is NP-complete for any dimension D greater than or equal to 2 and P greater than or equal to 3 non-parallel X-rays, and that it can be solved in polynomial time otherwise Ryser (Mathematical Association of America and Quinn & Boden, Rahway, New Jersey, 1963). The NP-completeness result above clearly extends to any c (greater than or equal to) 2, and therefore when studying the polyatomic case we can assume that l = 2. As shown in another article by the same authors (Gardner et al., Theoret. Comput. Sci. (1997), to appear), this problem is also NP-complete for c greater than or equal to 6 atoms, even for dimension D = 2 and axis-parallel X-rays. Gardner et al. (1997) conjecture that the problem remains NP-complete for c = 3, 4, 5, although, as they point out, the proof idea in Gardner ct al. (1997) does not seem to extend to c less than or equal to 5. We resolve the conjecture from Gardner et al. (1997) by proving that the problem is indeed NP-complete for c greater than or equal to 3 in 2D, even for axis-parallel X-rays. Our construction relies heavily on some structure results for the realizations of 0-1 matrices with given row and column sums. (C) 2001 Published by Elsevier Science B.V.