10
$\begingroup$

I'm wondering if the following problem is decidable in P-time (or even NP):

Given $a, b, c \in \mathbb{Z}$ and $m, n, p, q \in \mathbb{N}$ all in binary, decide if $a > br^m + cr^n$, where $r = {p \over q}$.

Remarks:

  1. If $c = 0$, this is a very special case of the following problem, which is in P for any fixed $n$ (Etessami et al.):

       Given $\vec{a}, \vec{b}, \vec{c}, \vec{d} \in \mathbb{N}^n$ all in binary, decide if $a_1^{b_1}\cdots a_n^{b_n} > c_1^{d_1}\cdots c_n^{d_n}$.

  1. An upper bound for the above problem is given by the fact that numerical analysis is in the counting hierarchy (Allender et al.)

  2. I'm particularly interested in values of $r$ very close to 1.

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.