<p>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.</p>

CC BY-SA 3.0
2016-11-01T09:18:05.380Z
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.
Sasho Nikolov
CC BY-SA 3.0
2016-11-01T14:04:57.437Z
@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...
Joshua Grochow
<cc.complexity-theory>
Complexity of finding primes in arithmetic progression
Dima
# Complexity of finding primes in arithmetic progression

(Asked by: username_0 on 2016-11-01)

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.

**Tags:** cc.complexity-theory

> **Comments:**
> **username_1**: 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.  
> **username_2**: @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...  

---

## 0 answers

