Tricolorable torus knots are NP-complete.
Peter B. GolbusRobert W. McGrailTomasz PrzytyckiMary SharacAleksandar ChakarovPublished in: ACM Southeast Regional Conference (2009)
Keyphrases
- np complete
- b spline
- randomly generated
- np hard
- satisfiability problem
- constraint satisfaction problems
- cubic spline
- computational complexity
- data complexity
- bounded treewidth
- massively parallel
- conjunctive queries
- polynomially solvable
- pspace complete
- data model
- bayesian networks
- information systems
- relational databases
- np complete problems
- database systems