On the computational complexity of determining polyatomic structures by X-rays

The problem of recovering the structure of crystalline materials from their discrete X-rays is of fundamental interest in many practical applications. An important special case concerns determining the position of atoms of several different types in the integer lattice, given the number of each type lying on each line parallel to some lattice directions. We show that the corresponding consistency problem is ℕℙ-complete for any two (or more) different (fixed) directions when six (or more) types of atoms are involved.