On the computational complexity of determining polyatomic structures by X-rays
Identifieur interne : 001102 ( Istex/Corpus ); précédent : 001101; suivant : 001103On the computational complexity of determining polyatomic structures by X-rays
Auteurs : R. J. Gardner ; P. Gritzmann ; D. PrangenbergSource :
- Theoretical Computer Science [ 0304-3975 ] ; 2000.
Abstract
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.
Url:
DOI: 10.1016/S0304-3975(97)00298-3
Links to Exploration step
ISTEX:C46DED77C24E5612284A1BB494E45C8BD493A9FALe document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title>On the computational complexity of determining polyatomic structures by X-rays</title><author><name sortKey="Gardner, R J" sort="Gardner, R J" uniqKey="Gardner R" first="R. J." last="Gardner">R. J. Gardner</name><affiliation><mods:affiliation>E-mail: gardner@baker.math.wwu.edu</mods:affiliation></affiliation><affiliation><mods:affiliation>Western Washington University, Department of Mathematics, Bellingham, WA 98225-9063, USA</mods:affiliation></affiliation></author><author><name sortKey="Gritzmann, P" sort="Gritzmann, P" uniqKey="Gritzmann P" first="P." last="Gritzmann">P. Gritzmann</name><affiliation><mods:affiliation>Technische Universität München, Zentrum Mathematik, D-80290 München, Germany</mods:affiliation></affiliation></author><author><name sortKey="Prangenberg, D" sort="Prangenberg, D" uniqKey="Prangenberg D" first="D." last="Prangenberg">D. Prangenberg</name><affiliation><mods:affiliation>Universität Trier, Fachbereich IV, Mathematik, Postfach 3825, D-54286 Trier, Germany</mods:affiliation></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:C46DED77C24E5612284A1BB494E45C8BD493A9FA</idno><date when="2000" year="2000">2000</date><idno type="doi">10.1016/S0304-3975(97)00298-3</idno><idno type="url">https://api.istex.fr/document/C46DED77C24E5612284A1BB494E45C8BD493A9FA/fulltext/pdf</idno><idno type="wicri:Area/Istex/Corpus">001102</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">001102</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a">On the computational complexity of determining polyatomic structures by X-rays</title><author><name sortKey="Gardner, R J" sort="Gardner, R J" uniqKey="Gardner R" first="R. J." last="Gardner">R. J. Gardner</name><affiliation><mods:affiliation>E-mail: gardner@baker.math.wwu.edu</mods:affiliation></affiliation><affiliation><mods:affiliation>Western Washington University, Department of Mathematics, Bellingham, WA 98225-9063, USA</mods:affiliation></affiliation></author><author><name sortKey="Gritzmann, P" sort="Gritzmann, P" uniqKey="Gritzmann P" first="P." last="Gritzmann">P. Gritzmann</name><affiliation><mods:affiliation>Technische Universität München, Zentrum Mathematik, D-80290 München, Germany</mods:affiliation></affiliation></author><author><name sortKey="Prangenberg, D" sort="Prangenberg, D" uniqKey="Prangenberg D" first="D." last="Prangenberg">D. Prangenberg</name><affiliation><mods:affiliation>Universität Trier, Fachbereich IV, Mathematik, Postfach 3825, D-54286 Trier, Germany</mods:affiliation></affiliation></author></analytic><monogr></monogr><series><title level="j">Theoretical Computer Science</title><title level="j" type="abbrev">TCS</title><idno type="ISSN">0304-3975</idno><imprint><publisher>ELSEVIER</publisher><date type="published" when="2000">2000</date><biblScope unit="volume">233</biblScope><biblScope unit="issue">1–2</biblScope><biblScope unit="page" from="91">91</biblScope><biblScope unit="page" to="106">106</biblScope></imprint><idno type="ISSN">0304-3975</idno></series><idno type="istex">C46DED77C24E5612284A1BB494E45C8BD493A9FA</idno><idno type="DOI">10.1016/S0304-3975(97)00298-3</idno><idno type="PII">S0304-3975(97)00298-3</idno></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">0304-3975</idno></seriesStmt></fileDesc><profileDesc><textClass></textClass><langUsage><language ident="en">en</language></langUsage></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">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.</div></front></TEI><istex><corpusName>elsevier</corpusName><author><json:item><name>R.J. Gardner</name><affiliations><json:string>E-mail: gardner@baker.math.wwu.edu</json:string><json:string>Western Washington University, Department of Mathematics, Bellingham, WA 98225-9063, USA</json:string></affiliations></json:item><json:item><name>P. Gritzmann</name><affiliations><json:string>Technische Universität München, Zentrum Mathematik, D-80290 München, Germany</json:string></affiliations></json:item><json:item><name>D. Prangenberg</name><affiliations><json:string>Universität Trier, Fachbereich IV, Mathematik, Postfach 3825, D-54286 Trier, Germany</json:string></affiliations></json:item></author><subject><json:item><lang><json:string>eng</json:string></lang><value>05</value></json:item><json:item><lang><json:string>eng</json:string></lang><value>68R</value></json:item><json:item><lang><json:string>eng</json:string></lang><value>69U</value></json:item><json:item><lang><json:string>eng</json:string></lang><value>82D</value></json:item><json:item><lang><json:string>eng</json:string></lang><value>90C</value></json:item><json:item><lang><json:string>eng</json:string></lang><value>92C</value></json:item><json:item><lang><json:string>eng</json:string></lang><value>Tomography</value></json:item><json:item><lang><json:string>eng</json:string></lang><value>Discrete tomography</value></json:item><json:item><lang><json:string>eng</json:string></lang><value>Computational complexity</value></json:item><json:item><lang><json:string>eng</json:string></lang><value>Polynomial-time algorithm</value></json:item><json:item><lang><json:string>eng</json:string></lang><value>NP-completeness</value></json:item><json:item><lang><json:string>eng</json:string></lang><value>Lattice</value></json:item><json:item><lang><json:string>eng</json:string></lang><value>Contingency table</value></json:item><json:item><lang><json:string>eng</json:string></lang><value>Data security</value></json:item><json:item><lang><json:string>eng</json:string></lang><value>Scheduling</value></json:item></subject><language><json:string>eng</json:string></language><originalGenre><json:string>Full-length article</json:string></originalGenre><abstract>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.</abstract><qualityIndicators><score>5.96</score><pdfVersion>1.2</pdfVersion><pdfPageSize>408 x 660 pts</pdfPageSize><refBibsNative>true</refBibsNative><keywordCount>15</keywordCount><abstractCharCount>521</abstractCharCount><pdfWordCount>6883</pdfWordCount><pdfCharCount>32270</pdfCharCount><pdfPageCount>16</pdfPageCount><abstractWordCount>80</abstractWordCount></qualityIndicators><title>On the computational complexity of determining polyatomic structures by X-rays</title><pii><json:string>S0304-3975(97)00298-3</json:string></pii><refBibs><json:item><author><json:item><name>A. Blass</name></json:item><json:item><name>Y. Gurevich</name></json:item></author><host><volume>55</volume><pages><last>88</last><first>80</first></pages><author></author><title>Inform. and Control</title></host><title>On the unique satisfiability problem</title></json:item><json:item><host><author></author></host></json:item><json:item><author><json:item><name>Y.-C. Chen</name></json:item><json:item><name>A. Shastri</name></json:item></author><host><volume>112</volume><pages><last>85</last><first>75</first></pages><author></author><title>Linear Algebra Appl.</title></host><title>On joint realization of (0,1) matrices</title></json:item><json:item><author><json:item><name>P.C. Fishburn</name></json:item><json:item><name>J.C. Lagarias</name></json:item><json:item><name>J.A. Reeds</name></json:item><json:item><name>L.A. Shepp</name></json:item></author><host><volume>91</volume><pages><last>159</last><first>149</first></pages><author></author><title>Discrete Math.</title></host><title>Sets uniquely determined by projections on axes. II. Discrete case</title></json:item><json:item><author><json:item><name>Z. Galil</name></json:item></author><host><volume>6</volume><pages><last>24</last><first>19</first></pages><issue>1</issue><author></author><title>SIGACT News</title></host><title>On some direct encodings of nondeterministic touring machines operating in polynomial time into P-complete problems</title></json:item><json:item><host><author></author></host></json:item><json:item><host><author></author></host></json:item><json:item><author><json:item><name>J.J. Gerbrands</name></json:item><json:item><name>C.H. Slump</name></json:item></author><host><volume>18</volume><pages><last>36</last><first>18</first></pages><author></author><title>Comput. Graphics Image Process.</title></host><title>A network flow approach to reconstruction of the left ventricle from two projections</title></json:item><json:item><author><json:item><name>R.W. Irving</name></json:item><json:item><name>M.R. Jerrum</name></json:item></author><host><volume>23</volume><pages><last>184</last><first>170</first></pages><author></author><title>SIAM J. Comput.</title></host><title>Three-dimensional statistical data security problems</title></json:item><json:item><host><author></author></host></json:item><json:item><author><json:item><name>C. Kisielowski</name></json:item><json:item><name>P. Schwander</name></json:item><json:item><name>F.H. Baumann</name></json:item><json:item><name>M. Seibt</name></json:item><json:item><name>Y. Kim</name></json:item><json:item><name>A. Ourmazd</name></json:item></author><host><volume>58</volume><pages><last>155</last><first>131</first></pages><author></author><title>Ultramicroscopy</title></host><title>An approach to quantitative high-resolution transmission electron microscopy of crystalline materials</title></json:item><json:item><author><json:item><name>C.H. Papadimitriou</name></json:item><json:item><name>M. Yannakakis</name></json:item></author><host><volume>28</volume><pages><last>259</last><first>244</first></pages><author></author><title>J. Comput. System. Sci.</title></host><title>The complexity of facets (and some facets of complexity)</title></json:item><json:item><host><author></author></host></json:item><json:item><author><json:item><name>P. Schwander</name></json:item><json:item><name>C. Kisielowski</name></json:item><json:item><name>M. Seibt</name></json:item><json:item><name>F.H, Baumann</name></json:item><json:item><name>Y. Kim</name></json:item><json:item><name>A. Ourmazd</name></json:item></author><host><volume>71</volume><pages><last>4153</last><first>4150</first></pages><author></author><title>Phys. Rev. Lett.</title></host><title>Mapping projected potential interfacial roughness, and composition in general crystalline solids by quantitative transmission electron microscopy</title></json:item><json:item><host><author></author></host></json:item></refBibs><genre><json:string>research-article</json:string></genre><host><volume>233</volume><pii><json:string>S0304-3975(00)X0126-0</json:string></pii><pages><last>106</last><first>91</first></pages><issn><json:string>0304-3975</json:string></issn><issue>1–2</issue><genre><json:string>journal</json:string></genre><language><json:string>unknown</json:string></language><title>Theoretical Computer Science</title><publicationDate>2000</publicationDate></host><categories><wos><json:string>science</json:string><json:string>computer science, theory & methods</json:string></wos><scienceMetrix><json:string>applied sciences</json:string><json:string>information & communication technologies</json:string><json:string>computation theory & mathematics</json:string></scienceMetrix></categories><publicationDate>2000</publicationDate><copyrightDate>2000</copyrightDate><doi><json:string>10.1016/S0304-3975(97)00298-3</json:string></doi><id>C46DED77C24E5612284A1BB494E45C8BD493A9FA</id><score>0.507267</score><fulltext><json:item><extension>pdf</extension><original>true</original><mimetype>application/pdf</mimetype><uri>https://api.istex.fr/document/C46DED77C24E5612284A1BB494E45C8BD493A9FA/fulltext/pdf</uri></json:item><json:item><extension>zip</extension><original>false</original><mimetype>application/zip</mimetype><uri>https://api.istex.fr/document/C46DED77C24E5612284A1BB494E45C8BD493A9FA/fulltext/zip</uri></json:item><istex:fulltextTEI uri="https://api.istex.fr/document/C46DED77C24E5612284A1BB494E45C8BD493A9FA/fulltext/tei"><teiHeader><fileDesc><titleStmt><title level="a">On the computational complexity of determining polyatomic structures by X-rays</title></titleStmt><publicationStmt><authority>ISTEX</authority><publisher>ELSEVIER</publisher><availability><p>©2000 Elsevier Science B.V.</p></availability><date>2000</date></publicationStmt><notesStmt><note>Communicated by M. Nivat</note></notesStmt><sourceDesc><biblStruct type="inbook"><analytic><title level="a">On the computational complexity of determining polyatomic structures by X-rays</title><author xml:id="author-1"><persName><forename type="first">R.J.</forename><surname>Gardner</surname></persName><email>gardner@baker.math.wwu.edu</email><note type="biography">Supported in part by the Alexander von Humboldt Foundation and by National Science Foundation Grant DMS-9501289.</note><note type="correspondence"><p>Corresponding author</p></note><affiliation>Supported in part by the Alexander von Humboldt Foundation and by National Science Foundation Grant DMS-9501289.</affiliation><affiliation>Western Washington University, Department of Mathematics, Bellingham, WA 98225-9063, USA</affiliation></author><author xml:id="author-2"><persName><forename type="first">P.</forename><surname>Gritzmann</surname></persName><note type="biography">Supported in part by the Deutsche Forschungsgemeinschaft and by a Max Planck Research Award.</note><affiliation>Supported in part by the Deutsche Forschungsgemeinschaft and by a Max Planck Research Award.</affiliation><affiliation>Technische Universität München, Zentrum Mathematik, D-80290 München, Germany</affiliation></author><author xml:id="author-3"><persName><forename type="first">D.</forename><surname>Prangenberg</surname></persName><note type="biography">Supported by the Deutsche Forschungsgemeinschaft through the “Graduiertenkolleg Mathematische Optimierung” at the Universität Trier.</note><affiliation>Supported by the Deutsche Forschungsgemeinschaft through the “Graduiertenkolleg Mathematische Optimierung” at the Universität Trier.</affiliation><affiliation>Universität Trier, Fachbereich IV, Mathematik, Postfach 3825, D-54286 Trier, Germany</affiliation></author></analytic><monogr><title level="j">Theoretical Computer Science</title><title level="j" type="abbrev">TCS</title><idno type="pISSN">0304-3975</idno><idno type="PII">S0304-3975(00)X0126-0</idno><imprint><publisher>ELSEVIER</publisher><date type="published" when="2000"></date><biblScope unit="volume">233</biblScope><biblScope unit="issue">1–2</biblScope><biblScope unit="page" from="91">91</biblScope><biblScope unit="page" to="106">106</biblScope></imprint></monogr><idno type="istex">C46DED77C24E5612284A1BB494E45C8BD493A9FA</idno><idno type="DOI">10.1016/S0304-3975(97)00298-3</idno><idno type="PII">S0304-3975(97)00298-3</idno></biblStruct></sourceDesc></fileDesc><profileDesc><creation><date>2000</date></creation><langUsage><language ident="en">en</language></langUsage><abstract xml:lang="en"><p>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.</p></abstract><textClass><keywords scheme="keyword"><list><head>MSC</head><item><term>05</term></item><item><term>68R</term></item><item><term>69U</term></item><item><term>82D</term></item><item><term>90C</term></item><item><term>92C</term></item></list></keywords></textClass><textClass><keywords scheme="keyword"><list><head>Keywords</head><item><term>Tomography</term></item><item><term>Discrete tomography</term></item><item><term>Computational complexity</term></item><item><term>Polynomial-time algorithm</term></item><item><term>NP-completeness</term></item><item><term>Lattice</term></item><item><term>Contingency table</term></item><item><term>Data security</term></item><item><term>Scheduling</term></item></list></keywords></textClass></profileDesc><revisionDesc><change when="1997-12-01">Modified</change><change when="2000">Published</change></revisionDesc></teiHeader></istex:fulltextTEI><json:item><extension>txt</extension><original>false</original><mimetype>text/plain</mimetype><uri>https://api.istex.fr/document/C46DED77C24E5612284A1BB494E45C8BD493A9FA/fulltext/txt</uri></json:item></fulltext><metadata><istex:metadataXml wicri:clean="Elsevier, elements deleted: tail"><istex:xmlDeclaration>version="1.0" encoding="utf-8"</istex:xmlDeclaration><istex:docType PUBLIC="-//ES//DTD journal article DTD version 4.5.2//EN//XML" URI="art452.dtd" name="istex:docType"></istex:docType><istex:document><converted-article version="4.5.2" docsubtype="fla"><item-info><jid>TCS</jid><aid>2831</aid><ce:pii>S0304-3975(97)00298-3</ce:pii><ce:doi>10.1016/S0304-3975(97)00298-3</ce:doi><ce:copyright type="full-transfer" year="2000">Elsevier Science B.V.</ce:copyright></item-info><head><ce:title>On the computational complexity of determining polyatomic structures by X-rays</ce:title><ce:author-group><ce:author><ce:given-name>R.J.</ce:given-name><ce:surname>Gardner</ce:surname><ce:cross-ref refid="FN1"><ce:sup>1</ce:sup></ce:cross-ref><ce:cross-ref refid="AFF1"><ce:sup>a</ce:sup></ce:cross-ref><ce:cross-ref refid="COR1">*</ce:cross-ref><ce:e-address>gardner@baker.math.wwu.edu</ce:e-address></ce:author><ce:author><ce:given-name>P.</ce:given-name><ce:surname>Gritzmann</ce:surname><ce:cross-ref refid="FN2"><ce:sup>2</ce:sup></ce:cross-ref><ce:cross-ref refid="AFF2"><ce:sup>b</ce:sup></ce:cross-ref></ce:author><ce:author><ce:given-name>D.</ce:given-name><ce:surname>Prangenberg</ce:surname><ce:cross-ref refid="FN3"><ce:sup>3</ce:sup></ce:cross-ref><ce:cross-ref refid="AFF3"><ce:sup>c</ce:sup></ce:cross-ref></ce:author><ce:affiliation id="AFF1"><ce:label>a</ce:label><ce:textfn>Western Washington University, Department of Mathematics, Bellingham, WA 98225-9063, USA</ce:textfn></ce:affiliation><ce:affiliation id="AFF2"><ce:label>b</ce:label><ce:textfn>Technische Universität München, Zentrum Mathematik, D-80290 München, Germany</ce:textfn></ce:affiliation><ce:affiliation id="AFF3"><ce:label>c</ce:label><ce:textfn>Universität Trier, Fachbereich IV, Mathematik, Postfach 3825, D-54286 Trier, Germany</ce:textfn></ce:affiliation><ce:correspondence id="COR1"><ce:label>*</ce:label><ce:text>Corresponding author</ce:text></ce:correspondence><ce:footnote id="FN1"><ce:label>1</ce:label><ce:note-para>Supported in part by the Alexander von Humboldt Foundation and by National Science Foundation Grant DMS-9501289.</ce:note-para></ce:footnote><ce:footnote id="FN2"><ce:label>2</ce:label><ce:note-para>Supported in part by the Deutsche Forschungsgemeinschaft and by a Max Planck Research Award.</ce:note-para></ce:footnote><ce:footnote id="FN3"><ce:label>3</ce:label><ce:note-para>Supported by the Deutsche Forschungsgemeinschaft through the “Graduiertenkolleg Mathematische Optimierung” at the Universität Trier.</ce:note-para></ce:footnote></ce:author-group><ce:date-received day="1" month="5" year="1997"></ce:date-received><ce:date-revised day="1" month="12" year="1997"></ce:date-revised><ce:miscellaneous>Communicated by M. Nivat</ce:miscellaneous><ce:abstract><ce:section-title>Abstract</ce:section-title><ce:abstract-sec><ce:simple-para>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 <math altimg="si1.gif"><of>NP</of></math>-complete for any two (or more) different (fixed) directions when six (or more) types of atoms are involved.</ce:simple-para></ce:abstract-sec></ce:abstract><ce:keywords class="msc"><ce:section-title>MSC</ce:section-title><ce:keyword><ce:text>05</ce:text></ce:keyword><ce:keyword><ce:text>68R</ce:text></ce:keyword><ce:keyword><ce:text>69U</ce:text></ce:keyword><ce:keyword><ce:text>82D</ce:text></ce:keyword><ce:keyword><ce:text>90C</ce:text></ce:keyword><ce:keyword><ce:text>92C</ce:text></ce:keyword></ce:keywords><ce:keywords class="keyword"><ce:section-title>Keywords</ce:section-title><ce:keyword><ce:text>Tomography</ce:text></ce:keyword><ce:keyword><ce:text>Discrete tomography</ce:text></ce:keyword><ce:keyword><ce:text>Computational complexity</ce:text></ce:keyword><ce:keyword><ce:text>Polynomial-time algorithm</ce:text></ce:keyword><ce:keyword><ce:text><math altimg="si2.gif"><of>NP</of></math>-completeness</ce:text></ce:keyword><ce:keyword><ce:text>Lattice</ce:text></ce:keyword><ce:keyword><ce:text>Contingency table</ce:text></ce:keyword><ce:keyword><ce:text>Data security</ce:text></ce:keyword><ce:keyword><ce:text>Scheduling</ce:text></ce:keyword></ce:keywords></head></converted-article></istex:document></istex:metadataXml><mods version="3.6"><titleInfo><title>On the computational complexity of determining polyatomic structures by X-rays</title></titleInfo><titleInfo type="alternative" contentType="CDATA"><title>On the computational complexity of determining polyatomic structures by X-rays</title></titleInfo><name type="personal"><namePart type="given">R.J.</namePart><namePart type="family">Gardner</namePart><affiliation>E-mail: gardner@baker.math.wwu.edu</affiliation><affiliation>Western Washington University, Department of Mathematics, Bellingham, WA 98225-9063, USA</affiliation><description>Corresponding author</description><description>Supported in part by the Alexander von Humboldt Foundation and by National Science Foundation Grant DMS-9501289.</description><role><roleTerm type="text">author</roleTerm></role></name><name type="personal"><namePart type="given">P.</namePart><namePart type="family">Gritzmann</namePart><affiliation>Technische Universität München, Zentrum Mathematik, D-80290 München, Germany</affiliation><description>Supported in part by the Deutsche Forschungsgemeinschaft and by a Max Planck Research Award.</description><role><roleTerm type="text">author</roleTerm></role></name><name type="personal"><namePart type="given">D.</namePart><namePart type="family">Prangenberg</namePart><affiliation>Universität Trier, Fachbereich IV, Mathematik, Postfach 3825, D-54286 Trier, Germany</affiliation><description>Supported by the Deutsche Forschungsgemeinschaft through the “Graduiertenkolleg Mathematische Optimierung” at the Universität Trier.</description><role><roleTerm type="text">author</roleTerm></role></name><typeOfResource>text</typeOfResource><genre type="research-article" displayLabel="Full-length article"></genre><originInfo><publisher>ELSEVIER</publisher><dateIssued encoding="w3cdtf">2000</dateIssued><dateModified encoding="w3cdtf">1997-12-01</dateModified><copyrightDate encoding="w3cdtf">2000</copyrightDate></originInfo><language><languageTerm type="code" authority="iso639-2b">eng</languageTerm><languageTerm type="code" authority="rfc3066">en</languageTerm></language><physicalDescription><internetMediaType>text/html</internetMediaType></physicalDescription><abstract lang="en">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.</abstract><note>Communicated by M. Nivat</note><subject><genre>MSC</genre><topic>05</topic><topic>68R</topic><topic>69U</topic><topic>82D</topic><topic>90C</topic><topic>92C</topic></subject><subject><genre>Keywords</genre><topic>Tomography</topic><topic>Discrete tomography</topic><topic>Computational complexity</topic><topic>Polynomial-time algorithm</topic><topic>NP-completeness</topic><topic>Lattice</topic><topic>Contingency table</topic><topic>Data security</topic><topic>Scheduling</topic></subject><relatedItem type="host"><titleInfo><title>Theoretical Computer Science</title></titleInfo><titleInfo type="abbreviated"><title>TCS</title></titleInfo><genre type="journal">journal</genre><originInfo><dateIssued encoding="w3cdtf">20000228</dateIssued></originInfo><identifier type="ISSN">0304-3975</identifier><identifier type="PII">S0304-3975(00)X0126-0</identifier><part><date>20000228</date><detail type="volume"><number>233</number><caption>vol.</caption></detail><detail type="issue"><number>1–2</number><caption>no.</caption></detail><extent unit="issue pages"><start>1</start><end>328</end></extent><extent unit="pages"><start>91</start><end>106</end></extent></part></relatedItem><identifier type="istex">C46DED77C24E5612284A1BB494E45C8BD493A9FA</identifier><identifier type="DOI">10.1016/S0304-3975(97)00298-3</identifier><identifier type="PII">S0304-3975(97)00298-3</identifier><accessCondition type="use and reproduction" contentType="copyright">©2000 Elsevier Science B.V.</accessCondition><recordInfo><recordContentSource>ELSEVIER</recordContentSource><recordOrigin>Elsevier Science B.V., ©2000</recordOrigin></recordInfo></mods></metadata><serie></serie></istex></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Rhénanie/explor/UnivTrevesV1/Data/Istex/Corpus
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 001102 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Istex/Corpus/biblio.hfd -nk 001102 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Rhénanie
|area= UnivTrevesV1
|flux= Istex
|étape= Corpus
|type= RBID
|clé= ISTEX:C46DED77C24E5612284A1BB494E45C8BD493A9FA
|texte= On the computational complexity of determining polyatomic structures by X-rays
}}
| This area was generated with Dilib version V0.6.31. |  |