By the Green-Tao theorem the prime numbers contain arbitrarily long arithmetic progressions. What is the computational complexity of the search problem in which the input is a natural number k encoded in binary and the output can be any arithmetic progression of primes with k terms? If this is unknown then please provide upper and lower bounds.

  • 3
    $\begingroup$ You can't hope for very good bounds because I think Green and Tao give quite weak bounds on the range in which you can find primes in a $k$-term AP: something like $2^{{}^{.\,^{.\,^{2^{O(k)}}}}}$, where the height of the tower of 2s is constant. I think $k!$ is a conjectured bound. $\endgroup$ – Sasho Nikolov Nov 1 '16 at 9:18
  • 2
    $\begingroup$ @SashoNikolov: If the actual answer is $k!$, then at least the primes could be written down in exponential space, so there would be the plausibility of an EXP upper bound. Still leads me to wonder if there is an algorithm which, given a bounding function as a parameter (not input; e.g. the tower of 2s, or $k!$), has running time polynomial in the bound... $\endgroup$ – Joshua Grochow Nov 1 '16 at 14:04

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.