49 views

Skip to first unread message

Feb 13, 2011, 2:44:32 AM2/13/11

to sprouts-theory

In [1] it is shown that the problem of determining whether play from

an arbitrary sprouts position can continue for more than k moves is NP-

complete. The paper also shows that the analagous problem of

determining whether, when starting from an arbitrary sprouts position,

the game can end in fewer than k moves is also NP-complete. The proofs

are clever but simple, and proceed by reduction from Planar Cubic

Graph Maximum Independent Set, the NP-completeness of which was shown

in [2].

Since winning a game of sprouts amounts to controlling the number of

moves for which the game lasts, it's natural to ask whether a

particular sprouts position can last for more (or less) than k moves.

For example, one might ask whether the position consisting of two

initial spots can last for more than k=5 moves. Here, the answer is

clearly no. However, the results of [1] tell us that this is a hard

problem in general; computer scientists will be flabbergasted if an

efficient algorithm is ever found to answer this question for

arbitrary sprouts positions and arbitrary values of k.

[1] Baird & Schweitzer. Complexity of the Game of Sprouts. FCS'10 -

6th International Conference on Foundations of Computer Science

http://www.usafa.edu/df/dfe/dfer/centers/accr/docs/baird2010b.pdf

[2] Garey & Johnson. The Rectilinear Steiner Tree Problem is NP-

Complete. Siam J. Applied Math 6 (1977) 826-834. http://www.jstor.org/pss/2100192

an arbitrary sprouts position can continue for more than k moves is NP-

complete. The paper also shows that the analagous problem of

determining whether, when starting from an arbitrary sprouts position,

the game can end in fewer than k moves is also NP-complete. The proofs

are clever but simple, and proceed by reduction from Planar Cubic

Graph Maximum Independent Set, the NP-completeness of which was shown

in [2].

Since winning a game of sprouts amounts to controlling the number of

moves for which the game lasts, it's natural to ask whether a

particular sprouts position can last for more (or less) than k moves.

For example, one might ask whether the position consisting of two

initial spots can last for more than k=5 moves. Here, the answer is

clearly no. However, the results of [1] tell us that this is a hard

problem in general; computer scientists will be flabbergasted if an

efficient algorithm is ever found to answer this question for

arbitrary sprouts positions and arbitrary values of k.

[1] Baird & Schweitzer. Complexity of the Game of Sprouts. FCS'10 -

6th International Conference on Foundations of Computer Science

http://www.usafa.edu/df/dfe/dfer/centers/accr/docs/baird2010b.pdf

[2] Garey & Johnson. The Rectilinear Steiner Tree Problem is NP-

Complete. Siam J. Applied Math 6 (1977) 826-834. http://www.jstor.org/pss/2100192

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu