patternModerate
Complexity-theoretic difficulty of checking the value of $\pi(x)$?
Viewed 0 times
theoreticthecheckingvaluedifficultycomplexity
Problem
The prime-counting function, demoted $\pi(x)$, is defined as the number of prime numbers less than or equal to $x$.
We can define a decision problem from $\pi(x)$ as follows:
Given two numbers $x$ and $n$, written in binary, decide if $\pi(x) = n$.
A friend and I were talking about this problem earlier today. There's a pseudopolynomial-time algorithm for this problem - just count up to $x$, using trial division at each step to see how many of the numbers are prime, and check if that's equal to $n$. The problem is also in PSPACE, since the algorithm I just described can be implemented to use only polynomial auxiliary space.
However, I'm having trouble finding a way to place this problem into a lower complexity class. I can't see how to build a polynomial-time verifier for the problem, so I'm not sure whether it's in NP, and I can't think of a way to get it into the polynomial hierarchy at all.
What is the most appropriate complexity class for this problem?
Thanks!
We can define a decision problem from $\pi(x)$ as follows:
Given two numbers $x$ and $n$, written in binary, decide if $\pi(x) = n$.
A friend and I were talking about this problem earlier today. There's a pseudopolynomial-time algorithm for this problem - just count up to $x$, using trial division at each step to see how many of the numbers are prime, and check if that's equal to $n$. The problem is also in PSPACE, since the algorithm I just described can be implemented to use only polynomial auxiliary space.
However, I'm having trouble finding a way to place this problem into a lower complexity class. I can't see how to build a polynomial-time verifier for the problem, so I'm not sure whether it's in NP, and I can't think of a way to get it into the polynomial hierarchy at all.
What is the most appropriate complexity class for this problem?
Thanks!
Solution
This is very much an open problem. I'll sketch some classes that the problem could "naturally" fit in.
Your definition is somewhat awkward to work with, the problem is hard to fit in to any existing complexity class. The language you've defined is the intersection of the languages $\{(x,n)|\pi(x)\leq n\}$ and $\{(x,n)|\pi(x)\geq n\}$. So if for instance $\{(x,n)|\pi(x)\leq n\}$ was in class $K$ then $\{(x,n)|\pi(x)\geq n\}$ would be in $coK$. This makes giving a characterization of the language you've defined hard because one would have to state "the intersection of a language in $K$ with a language in $coK$" to give the tightest bound.
The problem "Compute $\pi(X)$" is a problem in $\#P$, where $\#P\subseteq FPSPACE$ is the class of problems of the form "Compute the number of accepting paths of a nondeterministic, polynomial TM". Clearly we can construct a nondeterministic TM that guesses a number $q \leq x$, and then (with AKS) tests whether $q$ is prime.
A decision variant of $\#P$ is $PP$, which is the class of languages that are of the form: "Given a nondeterministic polynomial TM, do at least half the computation paths accept?". Both $\{(x,n)|\pi(x)\leq n\}$ and $\{(x,n)|\pi(x)\geq n\}$ are probably reducible to a problem in $PP$ (by doing some fudging to the aforementioned TM to balance out the number of accepting paths).
Your definition is somewhat awkward to work with, the problem is hard to fit in to any existing complexity class. The language you've defined is the intersection of the languages $\{(x,n)|\pi(x)\leq n\}$ and $\{(x,n)|\pi(x)\geq n\}$. So if for instance $\{(x,n)|\pi(x)\leq n\}$ was in class $K$ then $\{(x,n)|\pi(x)\geq n\}$ would be in $coK$. This makes giving a characterization of the language you've defined hard because one would have to state "the intersection of a language in $K$ with a language in $coK$" to give the tightest bound.
The problem "Compute $\pi(X)$" is a problem in $\#P$, where $\#P\subseteq FPSPACE$ is the class of problems of the form "Compute the number of accepting paths of a nondeterministic, polynomial TM". Clearly we can construct a nondeterministic TM that guesses a number $q \leq x$, and then (with AKS) tests whether $q$ is prime.
A decision variant of $\#P$ is $PP$, which is the class of languages that are of the form: "Given a nondeterministic polynomial TM, do at least half the computation paths accept?". Both $\{(x,n)|\pi(x)\leq n\}$ and $\{(x,n)|\pi(x)\geq n\}$ are probably reducible to a problem in $PP$ (by doing some fudging to the aforementioned TM to balance out the number of accepting paths).
Context
StackExchange Computer Science Q#43840, answer score: 11
Revisions (0)
No revisions yet.