On the computational complexity of determining polyatomic structures by X-rays. (English) Zbl 1005.82035
Summary: 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 NP-complete for any two (or more) different (fixed) directions when six (or more) types of atoms are involved.
MSC:
| 82D25 | Statistical mechanics of crystals |
| 92C55 | Biomedical imaging and signal processing |
| 05A99 | Enumerative combinatorics |
| 44A12 | Radon transform |
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
Keywords:
tomography; discrete tomography; computational complexity; polynomial-time algorithm; NP-completeness; lattice; contingency table; data security; schedulingReferences:
| [1] | Blass, A.; Gurevich, Y., On the unique satisfiability problem, Inform. and Control, 55, 80-88 (1982) · Zbl 0543.03027 |
| [2] | S.-K. Chang, The reconstruction of binary patters from their projections, Comm. ACM 14 (1971); S.-K. Chang, The reconstruction of binary patters from their projections, Comm. ACM 14 (1971) · Zbl 0214.42603 |
| [3] | Chen, Y.-C.; Shastri, A., On joint realization of (0,1) matrices, Linear Algebra Appl., 112, 75-85 (1989) · Zbl 0664.15006 |
| [4] | Fishburn, P. C.; Lagarias, J. C.; Reeds, J. A.; Shepp, L. A., Sets uniquely determined by projections on axes. II. Discrete case, Discrete Math., 91, 149-159 (1991) · Zbl 0752.44002 |
| [5] | Galil, Z., On some direct encodings of nondeterministic touring machines operating in polynomial time into P-complete problems, SIGACT News, 6, 1, 19-24 (1974) |
| [6] | R.J. Gardner, P. Gritzmann, D. Prangenberg, On the computational complexity of reconstructing lattice sets from their X-rays, preprint.; R.J. Gardner, P. Gritzmann, D. Prangenberg, On the computational complexity of reconstructing lattice sets from their X-rays, preprint. · Zbl 0947.68160 |
| [7] | R.J. Gardner, P. Gritzmann, D. Prangenberg, On the reconstruction of binary images from their discrete Radon transforms, in: R.A. Melter, A.Y. Wu, L. Latecki (eds.), Vision Geometry V, Society of Photo-Optical Instrumentation Engineers Proceedings, vol. 2826, 1996, pp. 121-132.; R.J. Gardner, P. Gritzmann, D. Prangenberg, On the reconstruction of binary images from their discrete Radon transforms, in: R.A. Melter, A.Y. Wu, L. Latecki (eds.), Vision Geometry V, Society of Photo-Optical Instrumentation Engineers Proceedings, vol. 2826, 1996, pp. 121-132. |
| [8] | Gerbrands, J. J.; Slump, C. H., A network flow approach to reconstruction of the left ventricle from two projections, Comput. Graphics Image Process., 18, 18-36 (1982) |
| [9] | Irving, R. W.; Jerrum, M. R., Three-dimensional statistical data security problems, SIAM J. Comput., 23, 170-184 (1994) · Zbl 0802.68046 |
| [10] | R. Karp, Reducibility among combinational problems, in: R.E. Miller, J.W. Thatcher (eds.), Plenum Press, New York, 1972, pp. 85-103.; R. Karp, Reducibility among combinational problems, in: R.E. Miller, J.W. Thatcher (eds.), Plenum Press, New York, 1972, pp. 85-103. |
| [11] | Kisielowski, C.; Schwander, P.; Baumann, F. H.; Seibt, M.; Kim, Y.; Ourmazd, A., An approach to quantitative high-resolution transmission electron microscopy of crystalline materials, Ultramicroscopy, 58, 131-155 (1995) |
| [12] | Papadimitriou, C. H.; Yannakakis, M., The complexity of facets (and some facets of complexity), J. Comput. System. Sci., 28, 244-259 (1984) · Zbl 0571.68028 |
| [13] | H.J. Ryser, Combinatorial Mathematics, Mathematical Association of America and Quinn & Boden, Rahway, NJ, 1963.; H.J. Ryser, Combinatorial Mathematics, Mathematical Association of America and Quinn & Boden, Rahway, NJ, 1963. · Zbl 0112.24806 |
| [14] | Schwander, P.; Kisielowski, C.; Seibt, M.; Baumann, F. H,; Kim, Y.; Ourmazd, A., Mapping projected potential interfacial roughness, and composition in general crystalline solids by quantitative transmission electron microscopy, Phys. Rev. Lett., 71, 4150-4153 (1993) |
| [15] | J. Simon, On some central problems in computational complexity, Ph.D. thesis, Dept. of Computer Science, Cornell University, Ithaca, NY, 1975.; J. Simon, On some central problems in computational complexity, Ph.D. thesis, Dept. of Computer Science, Cornell University, Ithaca, NY, 1975. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
