Return to Question

added 1001 characters in body

view source

edited Jun 26 2010 at 9:50

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.

added 176 characters in body

view source

edited Jun 26 2010 at 1:30

Swapnil Bhatia
161●1●10

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)?