Definition A problem is believed to be hard if there is no Polynomial Time algorithm that can solve it.