Domino Games and Complexity

DOI10.1137/0219055zbMath0711.68044OpenAlexW1979788764MaRDI QIDQ3495644

Erich Grädel

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

zbMATH Keywords

NP-completenesssatisfiability problemalternating Turing machinestiling systemscomplexity classpolynomial time hierarchyDomino games

Mathematics Subject Classification ID

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