In case P /= NP the gap doesn't necessarily have to be exponential, just superpolynomial (e.g. n^loglogn).