1
$\begingroup$

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.

|cite|improve this question
$\endgroup$
  • 2
    $\begingroup$ What is your proof for the empty language? $\endgroup$ – megas Mar 16 '15 at 2:44
  • 4
    $\begingroup$ 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. $\endgroup$ – Yuval Filmus Mar 16 '15 at 3:12
  • 1
    $\begingroup$ @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? $\endgroup$ – Raphael♦ Mar 16 '15 at 9:50
  • 2
    $\begingroup$ @Raphael Maybe we should leave it a week, since the asker explicitly asks for hints, rather than a full solution? $\endgroup$ – David Richerby Mar 16 '15 at 10:48
  • 1
    $\begingroup$ (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. $\endgroup$ – Luke Mathieson Mar 16 '15 at 12:07
4
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ Since the question asks for hints only, I've done that. If I remember, I'll come back in a week or so (say, around 23rd March) and flesh this out into a full answer for reference purposes. $\endgroup$ – David Richerby Mar 16 '15 at 10:50
  • 1
    $\begingroup$ You didn't remember. :) $\endgroup$ – aste123 Jul 21 '16 at 0:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.