Kaboozle Is NP-complete, Even in a Strip.
Tetsuo AsanoErik D. DemaineMartin L. DemaineRyuhei UeharaPublished in: FUN (2010)
Keyphrases
- np complete
- np hard
- randomly generated
- satisfiability problem
- computational complexity
- constraint satisfaction problems
- np complete problems
- conjunctive queries
- phase transition
- pspace complete
- upper bound
- polynomially solvable
- evolutionary algorithm
- decision making
- learning algorithm
- data sets
- database
- conp complete
- sat problem
- data complexity
- branch and bound algorithm
- query answering
- information retrieval