2
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Marzio De Biasi Feb 6 at 15:54
  • $\begingroup$ @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. $\endgroup$ – domotorp Feb 6 at 20:41
  • 1
    $\begingroup$ @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.). $\endgroup$ – Marzio De Biasi Feb 6 at 22:17
  • 3
    $\begingroup$ @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$). $\endgroup$ – Marzio De Biasi Feb 6 at 22:29

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.