Reconstructing Polyatomic Structures from Discrete X-Rays: NP-Completeness Proof for Three Atoms

We address a discrete tomography problem arising in the study of the atomic structure of crystal lattices. A polyatomic structure T is an integer lattice in dimension D ? 2, whose points may be occupied by c types of atoms. To “analyze” T, we conduct ? measurements that we refer to as discrete X-rays. A discrete X-ray in direction ? determines the number of atoms of each type on each line parallel to ?. Given such ? non-parallel X-rays, we wish to reconstruct T.The complexity of the problem for c = 1 (one atom) has been completely determined by Gardner, Gritzmann and Prangerberg, who proved that the problem is NP-complete for any dimension D ? 2 and ? ? 3 non-parallel X-rays, and that it can be solved in polynomial time otherwise.The NP-completeness result above clearly extends to any c ? 2, and therefore when studying the polyatomic case we can assume that ? = 2. As shown in another article by the same authors, this problem is also NP-complete for c ? 6 atoms, even for dimension D = 2 and for the axis-parallel X-rays. The authors of that article conjecture that the problem remains NP-complete for c = 3, 4, 5.We resolve this conjecture by proving that the problem is indeed NP-complete for c ? 3 in 2D, even for the 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.

ICSI Technical Report TR-98-012

Technical Report