How to deal with NP-complete and NP-hard Problems
Redefine the problem into Class P:
- RNA structure Tertiary => Secondary
- Alignment with arbitrary function=>constant
Worst-case exponential time:
- Devise exhaustive search algorithms.
- Exhaustive searching + Pruning.
Polynomial-time close-to-optimal solution:
- Exhaustive searching + Heuristics (Chess)
- Polynomial time approximation algorithms