Domino Games and Complexity
From MaRDI portal
Publication:3495644
DOI10.1137/0219055zbMath0711.68044OpenAlexW1979788764MaRDI QIDQ3495644
Publication date: 1990
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0219055
NP-completenesssatisfiability problemalternating Turing machinestiling systemscomplexity classpolynomial time hierarchyDomino games
2-person games (91A05) Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (8)
On the solvability of domino snake problems ⋮ Common knowledge and update in finite environments ⋮ Undecidability of domino games and hhp-bisimilarity. ⋮ The Three-Color and Two-Color TantrixTM Rotation Puzzle Problems Are NP-Complete Via Parsimonious Reductions ⋮ TANTRIX\(^{\text{TM}}\) rotation puzzles are intractable ⋮ The three-color and two-color Tantrix\(^{\text{TM}}\) rotation puzzle problems are NP-complete via parsimonious reductions ⋮ Complexity analysis of propositional concurrent programs using domino tiling ⋮ Simple sentences that are hard to decide
This page was built for publication: Domino Games and Complexity