On the reconstruction of binary and permutation matrices under (binary) tomographic constraints

The paper studies the problem of reconstructing binary matrices constrained by binary tomographic information. We prove new NP-hardness results that sharpen previous complexity results in the realm of discrete tomography but also allow applications to related problems for permutation matrices. Hence our results can be interpreted in terms of other combinatorial problems including the queens' problem. (c) 2008 Elsevier B.V. All rights reserved