The term "nearly linear time" is fine. The next part of that sentence is where the problem arises: it suggests that the opposite of "nearly linear", and the sta

The term "nearly linear time" is fine. The next part of that sentence is where the problem arises: it suggests that the opposite of "nearly linear", and the status quo, is that running time "increase[s] exponentially". But the existing standard algorithms already scale polynomially, not exponentially.