31
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ It is a little strange in your note that you refer to the "P=NP conjecture", because it is almost always conjectured that "P!=NP" $\endgroup$ – Sam Hopkins Aug 20 '18 at 1:51
  • $\begingroup$ Do you think it is better to refer to the "negation of P!=NP" conjecture? $\endgroup$ – Mark Sapir Aug 20 '18 at 2:03
  • $\begingroup$ I think the official name of the problem is P vs NP. And there are two mutually exclusive conjectures associated with the problem. $\endgroup$ – Mark Sapir Aug 20 '18 at 2:22
  • 1
    $\begingroup$ @SamHopkins: What you probably meant is that majority of scientists (97%?) believe that $P\ne NP $. That is certainly correct. In 1901 hundred % of scientists believed that Galilean relativity is the only relativity there is. Those 100% included Einstein. $\endgroup$ – Mark Sapir Aug 20 '18 at 10:27
  • $\begingroup$ @j.c. : Thank you for editing, I could not figure out how to do that on the phone. $\endgroup$ – Mark Sapir Aug 20 '18 at 13:24
24
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ It is very nice. Could you include a reference to a book where the terminology is introduced (the Wiki article is rather short)? We are going to include a reference to this answer in the updated version of our paper in arXiv and more references would benefit non-CS readers like myself. $\endgroup$ – Mark Sapir Aug 6 '18 at 13:40
  • $\begingroup$ ... also references to other terminology used in your answer (padding). $\endgroup$ – Mark Sapir Aug 6 '18 at 14:16
  • 1
    $\begingroup$ Hmm. Arora and Barak’s book has a decent introduction to alternating Turing machines in §5.3, including the definition of $\Sigma_i\text-\mathrm{TIME}(f(n))$, but they fall short of defining the exponential hierarchy $\Sigma^E_i=\Sigma_i\text-\mathrm{TIME}(2^{O(n)})$. They present a prototypical padding argument in §2.6.2. I will keep looking, but so far it seems that the exponential-time hierarchy may be a too specialized subject to be included in textbooks (though it is used in many research papers). $\endgroup$ – Emil Jeřábek supports Monica Aug 6 '18 at 14:41
  • 2
    $\begingroup$ The original reference for the exponential hierarchy seems to be Hartmanis, Immerman & Sewelson. (Warning: while their notation for $\Sigma^E_i$ agrees with the modern one, they write EXPTIME, NEXPTIME, and EXPH for what is nowadays denoted E, NE, and EH, not to what we denote EXP(TIME), NEXP(TIME), and EXPH.) $\endgroup$ – Emil Jeřábek supports Monica Aug 6 '18 at 15:18
  • 1
    $\begingroup$ My note with a reference to your answer is here: arxiv.org/abs/1808.05840 $\endgroup$ – Mark Sapir Aug 20 '18 at 0:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.