How hard are n2-hard problems?