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.

$\endgroup$
7
  • 2
    $\begingroup$ What is your proof for the empty language? $\endgroup$
    – megas
    Commented Mar 16, 2015 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$ Commented Mar 16, 2015 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
    Commented Mar 16, 2015 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$ Commented Mar 16, 2015 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$ Commented Mar 16, 2015 at 12:07

1 Answer 1

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.

$\endgroup$
2
  • 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$ Commented Mar 16, 2015 at 10:50
  • 1
    $\begingroup$ You didn't remember. :) $\endgroup$
    – aste123
    Commented Jul 21, 2016 at 0:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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