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

✍ Scribed by R.J. Gardner; P. Gritzmann; D. Prangenberg

• Publisher: Elsevier Science
• Year: 2000
• Tongue: English
• Weight: 297 KB
• Volume: 233
• Category: Article
• ISSN: 0304-3975
• DOI: 10.1016/s0304-3975(97)00298-3

✦ Synopsis

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 di erent 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 NP-complete for any two (or more) di erent (ÿxed) directions when six (or more) types of atoms are involved.