4
$\begingroup$

For positive integers $\hspace{.06 in}m_{\hspace{.02 in}0}\hspace{.02 in},n_0\hspace{.02 in},m_1,n_1\:$, $\;$ how difficult is it to decide whether $$\exp\left(\hspace{-0.03 in}\frac{m_{\hspace{.02 in}0}}{n_0}\hspace{-0.04 in}\right)-\frac{m_1}{n_1}$$ is positive or negative? $\;$ In particular, can that be decided in polynomial time?


(A consequence of the Lindemann-Weierstrass Theorem is that the above expression won't be zero.)

If it could be done efficiently, then that would give a way around the
table-maker's dilemma for the exponential and natural log functions.

$\endgroup$
  • $\begingroup$ Since the rationals are dense, I would guess arbitrarily difficult. $\endgroup$ – EuYu Sep 19 '13 at 5:42
  • $\begingroup$ I would guess it's about finding a sequence converging quickly towards $e^{\frac{m_0}{n_0}}$ while having a good error bound. A suggestion would be to use the power series definition on $e^{-\left|\frac{m_0}{n_0}\right|}$, since it's an alternating series, and thus the next term is a working error bound. This is doable in polynomial time to any given accuracy. $\endgroup$ – Arthur Sep 20 '13 at 7:45
  • $\begingroup$ It seems related to the result and discussion of this paper. $\endgroup$ – Clement C. Sep 21 '13 at 0:08

Your Answer

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