Tatamibari is NP-complete.

Aviv Adler Jeffrey Bosboom Erik D. Demaine Martin L. Demaine Quanquan C. Liu Jayson Lynch

Published in: CoRR (2020)

Keyphrases

np complete
randomly generated
np hard
constraint satisfaction problems
satisfiability problem
computational complexity
conjunctive queries
pspace complete
polynomial time complexity
phase transition
polynomially solvable
data complexity
bounded treewidth