3
$\begingroup$

The original problem of Domino Tiling and Wang Tile has great theoretical interest on computability theory... However, the great emerging problem on application of Wang Tile in material science and physics requires the tiling to satisfy one more condition:

The tiling should satisfy some proportionality, say, Tile 1 should appear with frequency 1/16, Tile 2 with frequency 9/16, Tile 3 with 6/16, Tile 4 with frequency 0...

The most important decision problem is the following: Could a given set of Tile tile a grid of size NxN satisfying the frequency constraint within a error of +-epsilon.

For example: could the set {Tile 1, Tile 2, Tile 3, Tile 4} tile the NxN grid with frequency 1/16+-0.01, 9/16+-0.01, 6/16+-0.01, 0+-0.01 respectively....

From one of my previous post:

practical algorithms for np complete problems

I realize the decision problem of tiling without such constraint could be modeled by SAT... With this constraint the problem becomes ridiculously difficult and I eagerly seek for solutions towards this finite decidable problem.... (we could forget epsilon for a moment if the problem with epsilon is too hard)...

Thank you.

For more detail why this problem is practical in material science and physics, see my previous post:

coloring in lattice

Reference for Wang Tile

Computational approach deciding whether a set of Wang Tile could tile the space up to some size

Improve this question
$\endgroup$
8
  • $\begingroup$ Since $N$ can typically be much bigger than the number of tile types, could you clarify: do you want the algorithm to be polynomial in $N$? (As opposed to $|N|$?) $\endgroup$
    – Joel David Hamkins
    Commented Apr 2, 2014 at 20:02
  • $\begingroup$ Indeed, the corresponding question in physics is that |N| us very huge (e.g. 10^6), but most them have frequency 0 (99.99%). However the epsilon would allow those with frequency 0 to appear just trying to make the tiling work..... While NxN could just be something like 1000x1000....If there is any polynomial algorithm correspond to any of them (either N or |N|), it would be great. $\endgroup$
    – user40780
    Commented Apr 2, 2014 at 20:12
  • $\begingroup$ In other words, speed corresponds to |N| is more important, thank you. $\endgroup$
    – user40780
    Commented Apr 2, 2014 at 21:02
  • $\begingroup$ I don't really understand your comment. My remark was that when it comes to polynomial time, we should probably be considering polynomials in N, in order to get the problem into NP, rather than polynomial in the length of the representation of N, that is, in $|N|$, by which I mean $\log_2(N)$. $\endgroup$
    – Joel David Hamkins
    Commented Apr 2, 2014 at 23:42
  • $\begingroup$ Oh... Sure, I mean polynomial in N... My comments just means that |T| (number of tiles) grows exponentially.... Sorry for the confusion... $\endgroup$
    – user40780
    Commented Apr 3, 2014 at 2:06

1 Answer 1

Reset to default
1
+100
$\begingroup$

The problem is NP-hard already if the frequency is 0 for every tile, see my answer for your earlier, related question: Conjecture on NP-completeness of tesselation of Wang Tile up to finite size

In case you don't like so many 0's, using the same trick you can leave every tile with even-even coordinates "blank" and force some tiles there, then you have a frequency 0.25.

If the given frequencies are positive only for finitely many tiles and they sum to 1, then this approach does not work.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thank you, even if this is NP-complete, do you think I could effectively programme and model this problem by any means? Thank you sooo much for your time and effort. $\endgroup$
    – user40780
    Commented Apr 4, 2014 at 0:57
  • $\begingroup$ Depending on the actual tile set and frequencies, brute force/dynamic programming might be efficient. Or you can just simply try an IP Solver. $\endgroup$
    – domotorp
    Commented Apr 4, 2014 at 4:18

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .