Title could also be "Researchers find a better heuristic for a class of exponentially scaling problems."

There's no claim to have changed the complexity class, so"exponentially faster" just means the problem is still exponentially in problem size, but the exponent is smaller.

From the looks of it, though, it is a nice result because it has pretty wide applicability.