Matching Modulo Associativity and Idempotency Is NP-Complete.
Ondrej KlímaJirí SrbaPublished in: MFCS (2000)
Keyphrases
- np complete
- randomly generated
- np hard
- pattern matching
- polynomial time complexity
- constraint satisfaction problems
- matching algorithm
- conjunctive queries
- np complete problems
- matching process
- satisfiability problem
- real time
- template matching
- computational complexity
- neural network
- databases
- graph matching
- data complexity
- pspace complete
- approximate matching