Another problem with NP-hard is that it only covers deterministic algorithms. Even if most instances of a problem are deterministically hard, they might still

Another problem with NP-hard is that it only covers deterministic algorithms. Even if most instances of a problem are deterministically hard, they might still have a randomized algorithm which solves them feasibly.