Languages in P that are not P-complete

Question

Why aren't there any languages in P that are not P-complete?

Answer 1

There are, for example

• the full language (i.e. answers $\mathtt{yes}$ for every instance),
• the empty language (i.e. answers $\mathtt{no}$ each time).

With regard to other languages, it depends what kind of reductions you consider. The most common are polynomial-time reductions (and those are assumed unless specified otherwise), and since your are talking about problems in $P$, then the reduction itself can solve the problem. In other words, any problem in $P$ can be polynomial-time reduced to any other non-trivial problem in $P$.

Of course, you can consider other kind of reductions, e.g. logarithmic-time. The problem with those is that with such a reduction you are unable to see the whole input (that would take linear time, that is, polynomial time), so there are very few things you could do, and therefore such reductions aren't much interesting.

I hope this helps $\ddot\smile$