1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

  1. Dec 2, 2015 #1
    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. jcsd
  3. Dec 2, 2015 #2

    jedishrfu

    Staff: Mentor

  4. Dec 2, 2015 #3
    Then why ø and {0,1} are not complete for P (polynomial) ??
     
  5. Dec 2, 2015 #4

    jedishrfu

    Staff: Mentor

    What is the context of your question? What subject are you studying? Math or computer science?
     
  6. Dec 2, 2015 #5
    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 ??
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: What does it mean for a language not to be complete?
  1. What does this mean? (Replies: 7)

Loading...