Theorem 2. For any k ≥ 3, it is NP-hard to find the longest play from a pattern of n dots, or even to find a play of length within n^(1-ε) of the longest play, for any constant ε > 0. This result holds for both variants of the game.
In their paper, k is the number of segments in a line (joining k+1 dots). And n is the number of dots in the initial pattern. Both variants are Touching and Disjoint.
« Older Frederica Sagor Maas dies at 111; silent film scre... | Seven Nation Army (original) -... Newer »
This thread has been archived and is closed to new comments
Buy a Shirt