Misère Partizan Arc Kayles is PSPACE-complete, even on Planar Graphs
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866908677640814592 |
|---|---|
| author | Burke, Kyle Cashman, Caroline Davies, Alfie Yoshiwatari, Kanae Yu, Francesca |
| author_facet | Burke, Kyle Cashman, Caroline Davies, Alfie Yoshiwatari, Kanae Yu, Francesca |
| contents | We show that Misère Partizan Arc Kayles is PSPACE-complete on planar graphs via a reduction from Bounded Two-Player Constraint Logic. Furthermore, we show how to embed our gadgets onto the square and triangular grids. In order to clearly explain these results, we get into the details of Bounded Two-Player Constraint Logic and find three PSPACE-complete variants of that as well. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_21888 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Misère Partizan Arc Kayles is PSPACE-complete, even on Planar Graphs Burke, Kyle Cashman, Caroline Davies, Alfie Yoshiwatari, Kanae Yu, Francesca Computational Complexity Discrete Mathematics Combinatorics 91A46 F.1.3; G.2.1 We show that Misère Partizan Arc Kayles is PSPACE-complete on planar graphs via a reduction from Bounded Two-Player Constraint Logic. Furthermore, we show how to embed our gadgets onto the square and triangular grids. In order to clearly explain these results, we get into the details of Bounded Two-Player Constraint Logic and find three PSPACE-complete variants of that as well. |
| title | Misère Partizan Arc Kayles is PSPACE-complete, even on Planar Graphs |
| topic | Computational Complexity Discrete Mathematics Combinatorics 91A46 F.1.3; G.2.1 |
| url | https://arxiv.org/abs/2511.21888 |