{"entities":{"Q5941271":{"pageid":8118073,"ns":120,"title":"Item:Q5941271","lastrevid":47658256,"modified":"2026-01-02T08:53:40Z","type":"item","id":"Q5941271","labels":{"en":{"language":"en","value":"Reconstructing polyatomic structures from discrete X-rays: NP-completeness proof for three atoms"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1635436"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5941271$686720E1-E046-4AD1-92C2-94CE247C43A6","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"aed70a8ddd992308b8d7b16e4e4f3143bfbb5ae9","datavalue":{"value":{"text":"Reconstructing polyatomic structures from discrete X-rays: NP-completeness proof for three atoms","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5941271$F194D783-645A-45A6-B18E-D08B306081F3","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"d3bf6f0670c731cb03f0ff580452e266ac8b12ae","datavalue":{"value":"0974.68219","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5941271$C885F4F7-0EC7-4FE8-AE21-39A3A96A197A","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"afc243a5243d451154b5b9ed28e2f8993b88dffa","datavalue":{"value":"10.1016/S0304-3975(99)00325-4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5941271$B209D3EF-3CCF-4091-A841-FBF65A089341","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"97f37dc983198355fd189ee54af7058c412c3222","datavalue":{"value":{"entity-type":"item","numeric-id":287139,"id":"Q287139"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5941271$6016610F-53D6-4EA4-8643-68AA56C8535D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"9e6830d8f79781e56e19a9648de13323b1402df1","datavalue":{"value":{"entity-type":"item","numeric-id":423917,"id":"Q423917"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5941271$1951746A-C9A0-49E7-A0EB-AFF125B8A343","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5941271$B6D347A5-BC19-40DE-860A-F864AEED3D68","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"0d780905acb67c2b1b938af03e08b68df411214b","datavalue":{"value":{"time":"+2001-08-20T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q5941271$B6A78801-CCAB-4455-8157-1AB088333EFA","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"73e35a1a0291ea0a02398ef29edbdd77fc298b8c","datavalue":{"value":"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\\geqslant 2\\), whose points may be occupied by \\(c\\) distinct types of atoms. To ``analyze'' \\(T,\\) we conduct \\(\\ell\\) measurements that we call discrete X-rays. A discrete X-ray in direction \\(\\xi\\) determines the number of atoms of each type on each line parallel to \\(\\xi\\). Given \\(\\ell\\) 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 \\textit{R. J. Gardner, P. Gritzmann} and \\textit{D. Prangenberg} [(*) Discrete Math. 202, No. 1-3, 45-71 (1999; Zbl 0947.68160)], who proved that the problem is NP-complete for any dimension \\(D\\geqslant 2\\) and \\(\\ell \\geqslant 3\\) non-parallel X-rays, and that it can be solved in polynomial time otherwise \\textit{H. J. Ryser} [Combinatorial mathematics (1963; Zbl 0112.24806)]. The NP-completeness result above clearly extends to any \\(c \\geqslant 2\\), and therefore when studying the polyatomic case we can assume that \\(\\ell=2\\). As shown in another article by the same authors [Theor. Comput. Sci. (to appear)], this problem is also NP-complete for \\(c\\geqslant 6\\) atoms, even for dimension \\(D=2\\) and axis-parallel X-rays. In (*) the authors conjecture that the problem remains NP-complete for \\(c=3,4,5,\\) although, as they point out, the proof idea in (*) does not seem to extend to \\(c<5.\\) We resolve the conjecture from (*) by proving that the problem is indeed NP-complete for \\(c\\geqslant 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.","type":"string"},"datatype":"string"},"type":"statement","id":"Q5941271$A5FCF641-618D-4641-8D3B-0A31E9029345","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"159426a5937e62cfbbcc198dd4848ab52d6e715e","datavalue":{"value":"68U05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5941271$B8A43652-46B8-45A2-A627-DAD7900C03AB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5941271$516B001A-5288-4680-B941-E4286FC0AA48","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e402ef99c8e0f5ecec9caa212271be1d3e4c4885","datavalue":{"value":"92C55","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5941271$E122CA84-430C-43B4-ACE8-A454048813A7","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"19fa6683b1520de4a7c64839d87e29422cba996a","datavalue":{"value":"1635436","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5941271$53701272-7683-4C14-BA4A-01830E64A250","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"282d44bb5d6ec3c6a7df0add723c7885edb872be","datavalue":{"value":"discrete tomography","type":"string"},"datatype":"string"},"type":"statement","id":"Q5941271$80A47F97-BA7D-45AD-B254-3FAFC90684D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"16c5974ed49697080d8bdc6ac2b83e2a55a1ca0a","datavalue":{"value":"high-resolution transmission electron microscope","type":"string"},"datatype":"string"},"type":"statement","id":"Q5941271$7D9B40CA-2A86-4535-BC53-D1C590E8D6F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2afe4361fb49b26bafb2920b3a7e4e38729d6875","datavalue":{"value":"multi-commodity max flow","type":"string"},"datatype":"string"},"type":"statement","id":"Q5941271$3D5BC199-A2BE-4025-9408-CC4F67587079","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5941271$CFE72179-9CA5-40DB-9518-F27B593E7C03","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"0d66b668d62d8680416f5ca30a5fcd0415362617","datavalue":{"value":{"entity-type":"item","numeric-id":1146695,"id":"Q1146695"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5941271$2423EC15-AD5B-421E-8B34-211AA875C068","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"50bc26045e335bb944e7522e3406b5fda15ba6a8","datavalue":{"value":{"entity-type":"item","numeric-id":5617289,"id":"Q5617289"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5941271$DC82A7B6-209A-4ED9-A69B-80667B6CC297","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"55223ae6f91a9a3c0f6a3be0cfb6236eaf5fcb6a","datavalue":{"value":{"entity-type":"item","numeric-id":4132234,"id":"Q4132234"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5941271$B74B8A47-F32F-4C0B-A0CB-699947132FA4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"48ca587dd3e9eb7db46e2962bde8a4d289a738d5","datavalue":{"value":{"entity-type":"item","numeric-id":1575953,"id":"Q1575953"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5941271$4E1B3EBE-F38B-4553-8143-5D4B27730869","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4fc737bfa95cd710e4b4262889b7b3ac388f8bc0","datavalue":{"value":{"entity-type":"item","numeric-id":1301705,"id":"Q1301705"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5941271$91163018-C35C-4C9A-8C2E-9E7B12D98314","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5941271$14FE9D16-8A67-47A7-98E6-ED1EF8E1A700","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5f38c64cd60618fed394cd3dd1e59d7748b606df","datavalue":{"value":{"entity-type":"item","numeric-id":4286235,"id":"Q4286235"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5941271$58D46217-0C21-45D8-91D5-D01A411387EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cf4ef2a1a38b56c81df266118bb63175df99c046","datavalue":{"value":{"entity-type":"item","numeric-id":3851094,"id":"Q3851094"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5941271$4B02F831-4D25-4F40-9F1D-A4B61E3E2664","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d386fba4eabb7c219b9931b8e7ee072f25c2e0c4","datavalue":{"value":{"entity-type":"item","numeric-id":1575953,"id":"Q1575953"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f07ae1bc3727c18a3f58b40bc306064cd6985137","datavalue":{"value":{"amount":"+0.8911167979240417","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5941271$2D157980-5D27-41ED-98EB-771D0071BC44","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cf49d8c5e62a41ed2b7c772c8cf3be6616c7665c","datavalue":{"value":{"entity-type":"item","numeric-id":2712298,"id":"Q2712298"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c9792640ad15e7e43ed3c5f409693ddcfe5174d6","datavalue":{"value":{"amount":"+0.8381299376487732","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5941271$82D0CA11-01D5-49C2-B1D7-CC2D0519C942","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5a3ae4ea93c2cbad8280b54ca3d638a682336c71","datavalue":{"value":{"entity-type":"item","numeric-id":2902905,"id":"Q2902905"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c9792640ad15e7e43ed3c5f409693ddcfe5174d6","datavalue":{"value":{"amount":"+0.8381299376487732","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5941271$0F068B60-C913-4942-A90A-96242B489AB8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"063b5dff5bd9cd8b384a6bfa3ce7473dca09cd80","datavalue":{"value":{"entity-type":"item","numeric-id":1301705,"id":"Q1301705"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"693e520041009ec9a6649780e0f0c3b1fdfdb11f","datavalue":{"value":{"amount":"+0.8309088945388794","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5941271$5946D7E6-6587-4569-B2B5-9DD0A98D87F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a3482be6956c56c4fe91d76956c0666099780ffd","datavalue":{"value":{"entity-type":"item","numeric-id":2844604,"id":"Q2844604"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f74e037e7cf7dcc9928d28b6c015b9e1bf8f15f6","datavalue":{"value":{"amount":"+0.8309081196784973","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5941271$D0CADC3C-ABC9-4D56-8058-C496659EA474","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:5941271","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:5941271"}}}}}