# P-Completeness and Reducibility

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.

• What is your proof for the empty language? – megas Mar 16 '15 at 2:44
• To expand on megas' comment, the proof that $\{0,1\}^*$ is not P-complete is the same as the proof that $\emptyset$ isn't. Don't forget that you also have to show that any other language is P-complete with respect to polytime reductions. – Yuval Filmus Mar 16 '15 at 3:12
• @DavidRicherby Thanks. This is also a close fit. I could not find a perfect duplicate (i.e. with answers that focus on this issue) and are correct (there are a couple of answers that state P=P-complete under polytime many-one reductions). So maybe this is worth answering again, explicitly and clearly? – Raphael Mar 16 '15 at 9:50
• @Raphael Maybe we should leave it a week, since the asker explicitly asks for hints, rather than a full solution? – David Richerby Mar 16 '15 at 10:48
• (Warning work with David's hint before following the link, if you're stuck it takes it a bit further) .There's also a similar question here, but from the other end. – Luke Mathieson Mar 16 '15 at 12:07

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.