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

Abstract 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 ≥2, whose points may be occupied by c distinct types of atoms. To “analyze” T, we conduct ℓ measurements that we call 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 type) has been completely determined by Gardner, Gritzmann and Prangerberg [5], 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 [8]. 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, [4], this problem is also NP-complete for c ≥ 6 atoms, even for dimension D = 2 and axis-parallel X-rays. The authors of [4] conjecture that the problem remains NP-complete for c =3, 4, 5, although, as they point out, the proof idea in [4] does not seem to extend to c ≤ 5. We resolve the conjecture from [4] by proving that the problem is indeed NP-complete for c ≥ 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.

Authors

• Marek Chrobak
• Christoph Dürr

Keywords

No keywords are indexed for this paper.