The transposition median problem is NP-complete.
Martin BaderPublished in: Theor. Comput. Sci. (2011)
Keyphrases
- np complete
- np hard
- satisfiability problem
- computational complexity
- approximation algorithms
- constraint satisfaction problems
- polynomial time complexity
- randomly generated
- np complete problems
- conjunctive queries
- bounded treewidth
- median filter
- pspace complete
- real time
- conp complete
- neural network
- database
- phase transition
- data complexity
- sat problem
- search space
- image processing
- genetic algorithm
- approximate string matching