<p>Consider the question of counting Wang tilings on a torus. The decision version of this problem is known to be NP-complete. Is the counting version #P-complete?</p>

CC BY-SA 4.0
2019-02-06T15:54:46.060Z
Yes, the problem is #P-complete on simply connected regions (see Igor Pak and Jed Yang, "Tiling Simply Connected Regions with Rectangles"); on a torus you can add extra tiles to define the fixed outer boundary of a smaller simply connected inner region.
Marzio De Biasi
CC BY-SA 4.0
2019-02-06T20:41:28.580Z
@Marzio I'm not that sure it's so simple. Things might add up/cancel and counting for the whole torus might become easier than counting for just some subfamilies. Cf., Pak and Yang also cannot prove the same thing for rectangles.
domotorp
CC BY-SA 4.0
2019-02-06T22:17:47.090Z
@domotorp: yes, you're right; clearly if the number of tiles (colors) is not fixed, then there should be no problem: just add enough colors to define the boundary of the simply connected region and for each type of original tile add a variant that can hook exactly to one tile of the border. If the set of tiles is finite, then you must build some aperiodic structure ... but to be honest in this case I would be very interested also in the proof of NP-completeness on a torus or even on a rectangle (the standard proof uses colors on the boundary of a square region and didn't find any refer.).
Marzio De Biasi
CC BY-SA 4.0
2019-02-06T22:29:48.610Z
@domotorp: ... mmm ... it cannot be NP-complete with a fixed set ... because if the size of the torus (or the size of the rectangle without colors along the border) is given in unary, then the language is sparse :-). Noteworthy, the Pak and Yang result on simply connected regions uses a fixed set of tiles ($<10^6$).
Marzio De Biasi
<cc.complexity-theory><co.combinatorics>
Complexity of counting Wang tiles
BGJ
# Complexity of counting Wang tiles

(Asked by: username_0 on 2019-02-06)

Consider the question of counting Wang tilings on a torus. The decision version of this problem is known to be NP-complete. Is the counting version #P-complete?

**Tags:** cc.complexity-theory, co.combinatorics
> **Comments:**
> **username_1**: Yes, the problem is #P-complete on simply connected regions (see Igor Pak and Jed Yang, "Tiling Simply Connected Regions with Rectangles"); on a torus you can add extra tiles to define the fixed outer boundary of a smaller simply connected inner region.  
> **username_2**: @Marzio I'm not that sure it's so simple. Things might add up/cancel and counting for the whole torus might become easier than counting for just some subfamilies. Cf., Pak and Yang also cannot prove the same thing for rectangles.  
> **username_1**: @domotorp: yes, you're right; clearly if the number of tiles (colors) is not fixed, then there should be no problem: just add enough colors to define the boundary of the simply connected region and for each type of original tile add a variant that can hook exactly to one tile of the border. If the set of tiles is finite, then you must build some aperiodic structure ... but to be honest in this case I would be very interested also in the proof of NP-completeness on a torus or even on a rectangle (the standard proof uses colors on the boundary of a square region and didn't find any refer.).  
> **username_1**: @domotorp: ... mmm ... it cannot be NP-complete with a fixed set ... because if the size of the torus (or the size of the rectangle without colors along the border) is given in unary, then the language is sparse :-). Noteworthy, the Pak and Yang result on simply connected regions uses a fixed set of tiles ($<10^6$).  

---

## 0 answers

