# What does it mean for a language not to be complete?

1. Dec 2, 2015

### S.ALGH

Anyone can explain to me What does it mean for a language not to be complete?

for example P has 2 languages are not complete for P

ø and {0,1} are not complete for P.

2. Dec 2, 2015

3. Dec 2, 2015

### S.ALGH

Then why ø and {0,1} are not complete for P (polynomial) ??

4. Dec 2, 2015

### Staff: Mentor

What is the context of your question? What subject are you studying? Math or computer science?

5. Dec 2, 2015

### S.ALGH

it is computer science, and the question is : A language L is complete for a language class C with respect to polynomial time reduction if L belongs to C and L' <=p L for all L' belong to C. Show that ø and {0,1} are the only languages in P that are not complete for P with respect to polynomial time reductions.

I started solving the question by proving that L belongs to P, but I did not understand how to show that ø and {0,1} are the only languages in P that are not complete ??