Discrete tomography asks whether a picture on a grid can be rebuilt from its row and column sums. One version, tile-packing tomography, asks whether copies of a fixed tile can be placed without overlap so that every row and every column covers a prescribed number of cells. It has a clean complexity boundary. If the tile is a straight bar, the problem is solvable in polynomial time by network flow. Every other connected tile makes it NP-complete. This note asks the same question from the side of refutations: when a set of projections has no tiling, how long is the shortest proof of that fact in the proof systems that real solvers implicitly use? We expect the answer not to follow the P versus NP boundary. Even trivially easy instances, such as single cells with Ryser-type row and column sums, already contain the pigeonhole principle. That principle is exponentially hard for Resolution, the proof system behind conflict-driven SAT solvers. Cutting Planes and linear-programming refutations, by contrast, handle these instances in one step.
The payoff is twofold. For practitioners, it predicts which solver family will fail on which tomography instances, and why. For theory, it poses a new question. Easy bar instances are hard only for the weak system. Non-bar instances, we conjecture, are hard even for strong algebraic and semi-algebraic systems once the NP-hardness gadgets are built to preserve proof hardness. A secondary, clearly labelled aim carries the same boundary to infinite grids, where degree theory (the classification of problems by how much uncomputable information their solutions need) asks whether non-bar instances can force every solution to be uncomputable.
Core Claim
We claim that tile-packing tomography has a three-level proof-complexity profile rather than a two-level one.
At the first level, 1×1 cells and bars, unsatisfiable instances have polynomial-size refutations in Cutting Planes, which reasons with integer linear inequalities. They are also refuted at degree one in Sherali-Adams, the proof system that corresponds to linear-programming relaxations, with coefficients bounded by the grid size. Yet these same instances require exponential-size Resolution refutations. The reason is concrete. An $(n+1)\times n$ grid with every row sum and every column sum equal to 1 is exactly the onto pigeonhole principle, a classical exponential lower bound for Resolution.
At the second level, every non-bar tile, suitably built reductions carry proof lower bounds from hard propositional formulas into tomography instances. This yields, conjecturally, linear-degree lower bounds for Sherali-Adams and Nullstellensatz, and exponential lower bounds for Resolution that do not depend on counting.
The third level is the open question of whether Cutting Planes also fails on non-bar instances. If it does, then non-bar tiles defeat integer reasoning in a way that bars never do.
Relation to Prior Work
The tomography papers supply the objects and constrain the design. Tile-Packing Tomography Is NP-hard proves the universal bar/non-bar dichotomy by reducing from 3-color tomography. It sorts non-bar tiles into four classes by their "conflicting vectors" and uses Ryser's theorem to rule out spurious solutions. Reconstructing 3-Colored Grids from Horizontal and Vertical Projections Is NP-hard closes the color gap at $k=3$ through a Vertex Cover reduction. On tiling under tomographic constraints gives earlier hardness results for L-trominoes, dominoes and 2×2 squares. Tiling with bars under tomographic constraints gives the polynomial side. All of these prove statements about deciding instances. None measures how hard it is to certify that an instance has no solution. That is the gap we fill, and we reuse their gadgets as raw material.
On the proof-complexity side, Separations in Proof Complexity and TFNP plays two roles. It supplies the method. It also constrains the claim, because it shows that simulating Resolution in Sherali-Adams can require huge coefficients, and that unary Sherali-Adams does not polynomially simulate Resolution. Tomography row sums are naturally written in unary and bounded by the grid dimension, so the right system to measure for bars is unary Sherali-Adams rather than Sherali-Adams with arbitrary coefficients.
The degree-theory papers enter only in the secondary aim. Intrinsic Complexity of Recursive Functions on Natural Numbers with Standard Order shows that finite "block" structure determines a relation's degree spectrum. The degree spectrum is the set of Turing degrees the relation takes across computable copies of a structure. That paper suggests that local tile geometry could likewise govern the complexity of infinite solutions. Punctual Presentability in Certain Classes of Algebraic Structures provides the notion of presenting a structure without unbounded search.
Research Program
The first strand is the easy side. We will formalize the natural placement encoding, with one Boolean variable per possible tile placement, row and column equalities, and non-overlap constraints. For 1×1 cells we will show that the constraint matrix is totally unimodular. In that setting infeasibility is certified directly by linear-programming duality, which gives a degree-one refutation with small coefficients. We will also show that the onto pigeonhole instance embeds directly, so Resolution needs exponential size.
We will then extend this to horizontal and vertical bars. The placement encoding may not be totally unimodular there. We will test whether Cutting Planes can simulate the flow argument from Tiling with bars under tomographic constraints with polynomially many cuts. If it cannot, we will identify the auxiliary flow variables that are needed.
The second strand is the hard side. We will build reductions from unsatisfiable CNF formulas into non-bar tomography instances that are local: each tile variable depends on a bounded number of formula variables, and each gadget's constraints can be derived from a bounded-size fragment. Locality is the standard route by which lower bounds on Resolution width and on algebraic degree survive a reduction. The four-case gadgets of Tile-Packing Tomography Is NP-hard were built only for correctness. A key technical step is to check whether they are local in this sense, or to redesign them for the L-tromino and 2×2 cases first. The target theorem is the following: for each non-bar tile $T$, there are unsatisfiable $m\times m$ instances whose Sherali-Adams and Nullstellensatz refutations need degree $\Omega(m^{c})$, for some constant $c>0$ depending on the gadget blow-up.
The third strand is secondary. On $\mathbb{Z}^2$ with computable row and column functions, a compactness argument puts the set of solutions in the class of sets definable by a computable tree of finite attempts. We will ask two questions. Does every solvable bar instance have a computable solution? Is there a non-bar instance that is solvable but has no computable solution? A positive answer to the second would be an infinite analogue of NP-hardness. We will pursue this only if the finite gadgets turn out to be periodic enough to be reused on the infinite grid.
Baselines
The naive reference point is exhaustive search over placements, and alongside it the plain linear-programming relaxation that drops integrality and declares infeasibility only when the relaxation itself is infeasible. By our theory the relaxation should refute every 1×1 instance and fail on every non-bar gadget instance. Matching that prediction exactly is the minimum bar the theory must clear.
The strongest competitor for general unsatisfiable Boolean instances is a conflict-driven clause-learning SAT solver run on a CNF encoding of the placement constraints. We will use the solver infrastructure in Saturn-code or a standard equivalent. Such solvers produce Resolution-style proofs, so they are the empirical face of our Resolution claims. The second strong competitor is a pseudo-Boolean solver that reasons with Cutting Planes, together with an integer-programming solver. These represent the proof systems we predict succeed on bars. We found no reported result on Lacuna for any SAT, pseudo-Boolean or integer-programming solver on tomography instances, so every baseline number will be produced here.
To keep the comparison fair, all solvers receive identical instances and the same wall-clock and memory limits on the same machine. Each solver gets its default configuration plus an equal, small tuning budget. Cardinality constraints are encoded in two standard ways so that no single CNF encoding is blamed for an effect.
The key ablation isolates the proof system. We keep the instance fixed and switch the CDCL solver between plain clausal reasoning and native cardinality reasoning. If our theory is right, turning cardinality reasoning on should remove the blow-up on bar instances and leave it in place on non-bar gadget instances. A second ablation compares our proof-preserving gadget instances against random unsatisfiable non-bar instances of the same size. This checks whether any hardness comes from the gadget design or merely from density.
The proposal is judged against a set of predictions rather than a performance target. We count it as having beaten these baselines if it correctly predicts, before any run, the growth rate of each solver family on each instance family, with bars exponential only for clausal solvers and gadget instances exponential for all. A solver log alone cannot supply that prediction.
Why not just…?
Why not just throw the instances at a good ILP or SAT solver and report runtimes? This is a real threat to the empirical half, and we include it as a baseline rather than avoid it. Its weakness is interpretation. A slow run does not tell us whether the cause is the encoding, the heuristics, or a lower bound in the proof system. The pigeonhole embedding shows that CDCL will blow up even on polynomial-time instances, so runtime alone would misclassify easy tomography as hard. The cardinality ablation separates the causes experimentally, and the theorems explain the result.
Why not just use the linear-programming relaxation, since tomography is an integer program? For 1×1 cells this is exactly right, and our first strand proves it. The open question is whether this extends beyond cells. The hardness proof in Tile-Packing Tomography Is NP-hard forces exact discrete configurations through affine independence. Separations in Proof Complexity and TFNP shows that low-coefficient linear reasoning cannot even simulate Resolution. Our degree lower bounds would show that no bounded number of Sherali-Adams lift-and-project rounds fixes the non-bar case. Measured integrality gaps on the gadget families will settle the question empirically.
Why not just simplify the four-case NP-hardness proof, a purely expository project? A unified invariant would be welcome. But simplification on its own does not say which certificates exist for unsatisfiable instances. Redesigning the gadgets for locality forces us to revisit the four cases anyway. We will report whether one invariant covers all four classes as a by-product, not as the goal.
Why bring in degree theory at all? Honestly, the finite results stand without it. The infinite question is included because nothing in the file addresses it and because it has a crisp answer either way. It is gated on the finite gadgets being reusable, and it will be dropped if they are not.
Proposed Experiments
We will generate four instance families. The first is onto-pigeonhole grids of growing $n$. The second is random unsatisfiable Gale-Ryser violations, meaning cell sums that fail Ryser's criterion. The third is unsatisfiable bar instances. The fourth is L-tromino and 2×2 gadget instances produced by our local reductions. As source formulas for the fourth family we use both random 3-CNF near threshold and the Hard UNSAT CNFs (31–50 clauses) from SATBench, described in SATBench: Benchmarking LLMs Logical Reasoning via Automated Puzzle Generation from SAT Formulas. The SATBench number most relevant here concerns language models, not solvers: o4-mini reaches 65.0% accuracy on Hard UNSAT. It indicates which formulas are hard for language-model reasoners, but it is not a solver baseline.
For each family we will run every baseline and record three quantities: solve time, the size of the proof log (for example, the number of learned clauses or cuts), and, for small grids, the exact minimum Sherali-Adams and Nullstellensatz degree computed by linear and polynomial solving. We will fit growth curves against grid side length.
The decisive checks are the following. On pigeonhole and Ryser-violating grids, clausal CDCL should grow exponentially while cardinality-aware and linear-programming solvers stay polynomial. If both stay polynomial, the encoding is leaking counting information and the Resolution claim must be restated for that encoding. On gadget instances, the measured minimum degree should grow with the source formula's known width, and cardinality reasoning should give no asymptotic relief. If it does give relief, Cutting Planes is strong on non-bar tiles and the third level of the claim is refuted, which is itself a publishable answer to the open question.
References
- Tile-Packing Tomography Is \mathbbNP{\mathbb{NP}}-hard
- Reconstructing 3-Colored Grids from Horizontal and Vertical Projections Is NP-hard
- On tiling under tomographic constraints
- Tiling with bars under tomographic constraints
- Separations in Proof Complexity and TFNP
- Intrinsic Complexity of Recursive Functions on Natural Numbers with Standard Order
- Punctual Presentability in Certain Classes of Algebraic Structures
- SATBench: Benchmarking LLMs Logical Reasoning via Automated Puzzle Generation from SAT Formulas