Chapter 5: Two Dimensions and Beyond

Section 7: Systems Based on Constraints

NP completeness [for 2D constraints]

The problem of whether a pattern can be found that satisfies a constraint even in a finite region is NP-complete. (See page 1145.) This suggests that to determine whether a repetitive pattern with repeating blocks of size n exists may in general take a number of steps which grows more rapidly than any polynomial in n.

From Stephen Wolfram: A New Kind of Science [citation]