How hard are n 2 -hard problems?
Stephen Bloch, Jonathan F. Buss, Judy Goldsmith · ACM SIGACT News · 1994
Many of the " n 2 -hard" problems described by Gajentaan and Overmars can be solved using limited nondeterminism or other sharply-bounded quantifiers. Thus we suggest that problems are not among the hardest problems solvable in quadratic time