Is this conjecture strictly weaker than P=NP?

Question

My three computability questions are related to the following group theory question (first asked by Bridson in 1996):

For which real $\alpha\ge 2$ the function $n^\alpha$ is equivalent to the Dehn function of a finitely presented group (i.e., what numbers belong to the isoperimetric spectrum)?

Clearly $\alpha\ge 1$ for every $\alpha$ in the isiperimetric spectrum, and by Gromov's theorem, the isoperimetric spectrum does not contains numbers from $(1,2)$.

In what follows, all functions are bounded by polynomials, so two functions $f(n), g(n)$ are equivalent if $af(n)<g(n)<bf(n)$ for some positive $a, b$. It is not necessary to know what the Dehn function of a group is (it is an important asymptotic invariant of a group). In this paper, we showed that if $\alpha\ge 4$ belongs to the isoperimetric spectrum if $\alpha$ can be computed by a non-deterministic Turing machine in time at most $2^{c2^m}$ for some $c>0$. Recently Olshanskii proved the same statement for all $\alpha\ge 2$ (the paper will appear in the Journal of Combinatorial Algebra). On the other hand if $\alpha$ is in the isoperimetric spectrum, then $\alpha$ can be computed in time at most $2^{2^{c2^{m}}}$ for some $c>0$. If P=NP, then one can reduce the number of 2's to two and bring the upper bound to be equal to the lower bound, completing the description of the isoperimetric spectrum. But the proof in our paper (Corollary 1.4) would give two 2's also if the following seemingly weaker conjecture holds.

Conjecture. Let $T(n)$ be the time function of a non-deterministic Turing machine which is between $n^2$ and $n^k$ for some $k$. Then there is a deterministic Turing machine $M$ computing a function $T'(n)$ which is equivalent to $T(n)$ and having time function at most $T(n)^c$ for some constant $c$ (depending on $T$). (For the definition of the time function see this question).

Question Is the conjecture strictly weaker than P=NP?

Update My note with a reference to Emil's answer is here.

Answer 1

The conjecture is indeed strictly weaker than $\mathrm{P = NP}$, in the sense that it follows from $\mathrm E=\Sigma^E_2$, which is not known to imply $\mathrm{P = NP}$. Of course, we cannot prove this unconditionally with current technology, as it would establish $\mathrm{P\ne NP}$.

Here, $\mathrm E$ denotes $\mathrm{DTIME}(2^{O(n)})$, $\mathrm{NE}$${}=\mathrm{NTIME}(2^{O(n)})$, and $\Sigma^E_2=\mathrm{NE^{NP}}$ is the second level of the exponential hierarchy (with linear exponent), $\mathrm{EH}$. (See e.g. [2]; warning: their notation for $\mathrm{(N)E}$ and $\mathrm{EH}$ is $\mathrm{(N)EXPTIME}$ and $\mathrm{EXPH}$, which are nowadays used for somewhat different classes.) Equivalently, we may define $\Sigma_2^E$ using alternating Turing machines (see [1,§5.3]) as $\Sigma^E_2=\Sigma_2\text-\mathrm{TIME}(2^{O(n)})$.

Note that conversely, $\mathrm{P = NP}$ implies $\mathrm{P=PH}$, which implies $\mathrm E = \Sigma^E_2=\mathrm{EH}$ by a padding argument similar to [1,§2.6.2].

To see that $\mathrm E = \Sigma^E_2$ implies the conjecture, let $t$ be the function defined exactly like $T$, but with the input and output integers written in binary, and let $g_t=\{(x,y):y\le t(x)\}$ be its subgraph. Then $g_t\in\Sigma^E_2$: in order to show $(x,y)\in g_t$, we only need to (nondeterministically) guess an input $w$ of the original NTM of length $x$ along with an accepting computation, and (co-nondeterministically) check that there is no accepting computation of length $<y$. This is a $\Sigma_2$-machine running in time polynomial in $x$, or exponential in the length of the binary representation of $x$.

So, if $\mathrm E = \Sigma^E_2$, then $g_t\in\mathrm E$. Then we can compute $t$ (as a function) deterministically in exponential time using binary search, and therefore we can compute $T(n)$ in time polynomial in $n$.

References:

[1] Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009.

[2] Juris Hartmanis, Neil Immerman, and Vivian Sewelson, Sparse sets in NP−P: EXPTIME versus NEXPTIME, Information and Control 65 (1985), no. 2–3, pp. 158–181, doi: 10.1016/S0019-9958(85)80004-8.