NP Complete means that a problem must at least be in the set NP, but may be worse Running Time.