On Thu, Mar 1, 2018 at 8:15 PM, Cris Moore <moore@santafe.edu> wrote:
On Mar 1, 2018, at 3:56 PM, Josh Jordan <josh@joshjordan.name> wrote:
On Thu, Mar 1, 2018 at 4:12 PM, Mike Beeler <mikebeeler2@gmail.com> wrote:
I have sometimes wondered is there is any possible rigorous mathematical method for [solving polyomino packing problems].
The solubility of a 2-d polygon packing problem is equivalent to a sentence in the first-order theory of the reals. That theory is decidable, so, in theory, we could submit such a sentence to a decision procedure and wait for the answer.
I note that tiling a region with polyominoes is NP-complete, even if they are all copies of the L-tromino (an old result of mine with John Michael Robson).
And deciding even the existential theory of the reals is NP-hard [https://en.wikipedia.org/wiki/Existential_theory_of_the_reals], to say nothing of the general first-order theory. Note, though, that Mike didn't say anything about efficiency!