Zig-Zag Numberlink is NP-Complete.
Aaron B. AdcockErik D. DemaineMartin L. DemaineMichael P. O'BrienFelix ReidlFernando Sánchez VillaamilBlair D. SullivanPublished in: J. Inf. Process. (2015)
Keyphrases
- np complete
- np hard
- randomly generated
- satisfiability problem
- constraint satisfaction problems
- conjunctive queries
- pspace complete
- np complete problems
- sat problem
- polynomial time complexity
- constraint satisfaction
- computational complexity
- probabilistic model
- phase transition
- query processing
- data complexity
- upper bound
- special case
- lower bound
- objective function
- reinforcement learning