computational complexity - Completeness, easiest, hardest problems

One says that a language $L$ is complete for a complexity class $mathcal{C}$ if $L$ is in $mathcal{C}$ and every language in $mathcal{C}$ is reducible to $L$. Thus, in a sense, $L$ is the hardest language in $mathcal{C}$. For example, $3SAT$ is the hardest language in $mathcal{NP}$.

Now recall Rice's theorem: any nontrivial property of a language is undecidable. The proof of this theorem essentially rests on the fact that if any such property were decidable, then it could be used to decide the $HALTING$ language. Thus, in a sense, $HALTING$ is the easiest property of all properties.

And then here is a peculiar thing: the proof of Rice's theorem---at least the one I've seen---amounts to constructing a reduction from $HALTING$ to every property. Contrast this with the definition of completeness, and one realizes that these are ``opposites'' of each other in a sense.

Question: Is there more to this observation? Is there work done on this? If there are experts in the audience, could you elaborate on my observation? Does one ever consider ``easiest'' problems in complexity theory as in my example above, and if so, does it lead to interesting results (like it does to Rice's theorem above)?

Thank you in advance for your comments and your effort in reading and thinking my question.

Rev. 1:

Note that when I say $HALTING$ is the easiest property, I don't mean to imply that it is easy. Of course, it is an undecidable language. It is ``easy'' in a relative sense: every other property is at least as hard as $HALTING$, because if any other property can be decided, then it yields a decider for $HALTING$.

When we talk of an complete problem, we use similar terminology: if a language has a reduction from every other language in its class, then we call it complete and rightly refer to it as being one of the hardest languages in the class.

This is the subtle similarity / difference I am trying to point out. These two are in a sense opposites. In one case, we get reductions from all languages in the class. In the other, we get reductions from one language to all other languages in the class. In the first case, we call the target hardest. In the second, we (could) call the source the easiest.

I hope that this provides a clearer context for my question. Thanks.

• Next lo.logic - In set theories where Continuum Hypothesis is false, what are the new sets?
• Previous dg.differential geometry - A topological consequence of Riemann-Roch in the almost complex case