I am taking an algorithm analysis class and am stuck on one of my homework probl

Question

I am taking an algorithm analysis class and am stuck on one of my homework problems and would appreciate it if I could receive some guidance.

The problem I'm stuck on is proving that the empty language and {0,1}? are the only languages in P that are not complete for P with respect to polynomial-time reductions (problem 34.3-6 in CLRS 3rd edition). The first part of the problem seems fairly straightforward enough (proving the empty language criteria). However, I'm not sure where to even begin when I have to prove the criteria for {0,1}?. I'm NOT looking for the answer, however I would appreciate some guidance on how I can begin to think about this problem.

Explanation / Answer

Hint. The definition of reduction from X to Y requires that "yes" instances of X be mapped to "yes" instances of Y and "no" instances to "no" instances.

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.