Zig-Zag Numberlink is NP-Complete.
Aaron B. AdcockErik D. DemaineMartin L. DemaineMichael P. O'BrienFelix ReidlFernando Sánchez VillaamilBlair D. SullivanPublished in: CoRR (2014)
Keyphrases
- np complete
- np hard
- satisfiability problem
- constraint satisfaction problems
- randomly generated
- conjunctive queries
- np complete problems
- polynomially solvable
- computational complexity
- pspace complete
- data complexity
- database systems
- phase transition
- learning algorithm
- data integration
- logic programs
- linear programming
- bounded treewidth
- special case
- computationally complex