My question is about the theory of complexity, but let me first explain my motivation, which comes from number theory or more precisely from trying to understand a question/conjecture of Serre and a remark he made about it. Yesterday at Harvard, Jean-Pierre Serre gave a wonderful colloquium on "Variation with $p$ of the number of solutions mod $p$ of a system of polynomial equations". There was many things in it, most of them I knew (but beautifully explained nevertheless), but some lines of thought seemed completely new (and at least they surely where for me):

Let $P(X)$ be a fixed non-zero polynomial in $\mathbb{Z}[X]$. Let us denote by $N(p)$ the number of solution of $P(X) \equiv 0 \pmod{p}$. Serre noticed that there was a very simple, efficient and old algorithm, already present in a paper by Galois and probably older (since Galois refers to it as well-known), to compute $N(p)$ for big values of $p$: compute by Euclid's method the gcd of $X^p-X$ and $P(X)$ in $\mathbb{Z}/p\mathbb{Z}[X]$. The degree of this polynomial is the number of solutions $N(p)$. The algorithm, Serre said, runs in $O(\log(p)^{2+\epsilon})$.

Now if it happens that all roots of $P(X)$ are in a cyclotomic fields (for example, a quadratic polynomial) then $N(p)$ is determined by some congruences, that is there is an $m$ such that $N(p)$ depends only on $p \pmod{m}$ (For $P$ quadratic, it is just the quadratic reciprocity law), and in this case, determining $N(p)$ can be made in $O(\log p)$ steps obviously.

Serre asked (or conjectured, I don't remember for sure the term he used) if conversely, the existence of an algorihhm in linear time $O(\log p)$ to compute $N(p)$ would imply that all roots of $P$ are in a cyclotomic field.

After that he made a remark that I didn't fully understand, that he had asked some friends that were specialists of complexity theory and and that they told him there were not theorem proving statement like "for a given problem, there is no algorithm solving it in linear time", but I am not sure if this was really that, nor if he was talking only of this specific problem or of all computable problems.

Well, my question just aims to understand Serre's remark

Do we know of a computable question (with answer yes or no) depending of a parameter $n$ such that the answer can be given in $O((\log n)^r)$ steps but provably not in $O((\log n)^s)$, where $1 \leq s < r$ are real numbers? If yes, how do we do that? If no, are there conjecture that for some problem it is not possible?

(Remark:the answer to the question of Serre is a natural integer, not yes or no, but since this integer is less than the degree of $P$, obviously it can be transformed into a finite set of "yes or no" questions).

I am an absolute beginner in complexity theory. I made some research on the web this morning and yesterday, but I didn't find an answer or anything close. My question may be very basic and a reference to a text discussing this kind of questions would be a perfectly nice answer.


1 Answer 1


Yes, if $1\le r< s$, there exists a set of integers computable in time $O((\log x)^s)$, but not in time $O((\log x)^r)$, where $x$ is the input number written in binary. This is an instance of the time hierarchy theorem. However, the only known such problems are obtained by diagonalization. There is no known natural problem (say, from number theory or combinatorics) that would be computable in polynomial time, but provably required more than linear time.

You can find a discussion of the time hierarchy theorem in any textbook on complexity theory. Two are mentioned in the Wikipedia article, another popular one is by Arora and Barak.

  • 3
    $\begingroup$ I should also stress that the “no natural problems” bit assumes a reasonable computation model. There are problems known to require super-linear time in some artificially restricted models: for example, recognition of palindromes on a single-tape Turing machines needs at least quadratic time (which is also sufficient), however it can be done in linear time using an auxiliary tape. $\endgroup$ Sep 23, 2011 at 17:32
  • $\begingroup$ Thanks Emil. That's exactly what I wanted to know. So I presume that answering Serre's question is hopeless in the current state of knowledge in complexity theory. Too bad... I liked that question a lot. $\endgroup$
    – Joël
    Sep 24, 2011 at 2:09
  • $\begingroup$ Also, the question itself assumes a reasonable computation model. For example, machines with an oracle containing $N(p)$ information for all primes $p$ will do much better on this particular problem, but will still polynomial-time compute the same things that a plain machine would. $\endgroup$ Sep 24, 2011 at 2:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.