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. 



Polynomial-time complexity and a question and a remark of Serre
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](http://en.wikipedia.org/wiki/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](http://www.cs.princeton.edu/theory/complexity/).


