0
$\begingroup$

Fix distinct primes $q_1,\dots,q_t\in[2^{m-1},2^m]$ and integers $r_i\in[0,q_i-1]$ at every $i\in\{1,\dots,t\}$.

Is there a way to exactly count the number of primes $a\equiv r_i\bmod q_i$ where $a\in[0,2^{n}]$ at every $i\in\{1,\dots,t\}$ in polynomial in $nt$ time at least under the conjecture $P=NP$?

Improve this question
$\endgroup$
4
  • 4
    $\begingroup$ Forget arithmetic progressions, do we even know if $\pi(x)$ is polytime computable assuming P=NP? $\endgroup$ Commented Mar 20 at 23:50
  • 1
    $\begingroup$ @Wojowu We do know how to compute approximately up to constant factors if $P=NP$ epubs.siam.org/doi/10.1137/0214060. $\endgroup$ Commented Mar 21 at 0:09
  • $\begingroup$ @Wojowu We do know Riemann Hypothesis counts better than previous comment's approach via the $li(x)$ function which is good up to $x^{\frac12+\epsilon}$ additive factor where $li(x)$ is the logarithmic integral function en.wikipedia.org/wiki/Logarithmic_integral_function but I do not know how fast $li(x)$ can be computed to closest decimal point. $\endgroup$ Commented Mar 21 at 0:25
  • 2
    $\begingroup$ I'm assuming you are referring to Theorem 3.1 of that paper. We don't even need RH to get approximation better than the paper you cite - the error term $li(n)-\pi(x)$ is $O(x/(\log x)^k)$ for all constants $k$. For any given $k$ we can get a more easily computable such approximation by taking the asymptotic expansion of $li(n)$. Either way, this doesn't get us any closer to computing the exact value. $\endgroup$ Commented Mar 21 at 1:47

0

Reset to default

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.