Computational Complexity of Swish
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866908764103245824 |
|---|---|
| author | Horiyama, Takashi Ito, Takehiro Kawahara, Jun Minato, Shin-ichi Suzuki, Akira Uehara, Ryuhei Yamaguchi, Yutaro |
| author_facet | Horiyama, Takashi Ito, Takehiro Kawahara, Jun Minato, Shin-ichi Suzuki, Akira Uehara, Ryuhei Yamaguchi, Yutaro |
| contents | Swish is a card game in which players are given cards having symbols (hoops and balls), and find a valid superposition of cards, called a "swish." Dailly, Lafourcade, and Marcadet (FUN 2024) studied a generalized version of Swish and showed that the problem is solvable in polynomial time with one symbol per card, while it is NP-complete with three or more symbols per card. In this paper, we resolve the previously open case of two symbols per card, which corresponds to the original game. We show that Swish is NP-complete for this case. Specifically, we prove the NP-hardness when the allowed transformations of cards are restricted to a single (horizontal or vertical) flip or 180-degree rotation, and extend the results to the original setting allowing all three transformations. In contrast, when neither transformation is allowed, we present a polynomial-time algorithm. Combining known and our results, we establish a complete characterization of the computational complexity of Swish with respect to both the number of symbols per card and the allowed transformations. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_09289 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Computational Complexity of Swish Horiyama, Takashi Ito, Takehiro Kawahara, Jun Minato, Shin-ichi Suzuki, Akira Uehara, Ryuhei Yamaguchi, Yutaro Data Structures and Algorithms Computational Complexity Combinatorics Swish is a card game in which players are given cards having symbols (hoops and balls), and find a valid superposition of cards, called a "swish." Dailly, Lafourcade, and Marcadet (FUN 2024) studied a generalized version of Swish and showed that the problem is solvable in polynomial time with one symbol per card, while it is NP-complete with three or more symbols per card. In this paper, we resolve the previously open case of two symbols per card, which corresponds to the original game. We show that Swish is NP-complete for this case. Specifically, we prove the NP-hardness when the allowed transformations of cards are restricted to a single (horizontal or vertical) flip or 180-degree rotation, and extend the results to the original setting allowing all three transformations. In contrast, when neither transformation is allowed, we present a polynomial-time algorithm. Combining known and our results, we establish a complete characterization of the computational complexity of Swish with respect to both the number of symbols per card and the allowed transformations. |
| title | Computational Complexity of Swish |
| topic | Data Structures and Algorithms Computational Complexity Combinatorics |
| url | https://arxiv.org/abs/2601.09289 |