Prove that PTIME has no complete problems with respect to linear-time reductions.
I know that PTIME means all these problems that we can solve them in polynomial time. I suppose that I should use here time hierarchy theorem - I know it.
However, I have no idea how to solve it. I am beginner at this subject so I ask for explanation for dummy :)
Suppose that you have a PTIME-complete problem $A$, with some algorithm that runs in $O(n^k)$ time.
This means, by definition, that every problem in PTIME can be decided by first running a linear-time reduction to $A$, and then running your supposed $O(n^k)$ solver for $A$ on the result.
Can you see how this contradicts the time hierarchy theorem?
(Hint. How large an $A$-instance does the linear-time reduction even have time to print?)