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

AI Thread Summary
A language is considered incomplete for a class if it cannot be used to solve all problems within that class through polynomial time reductions. In the context of polynomial time (P), the languages ø (empty language) and {0,1} are identified as not complete because they do not meet the criteria for completeness. The discussion revolves around understanding why these specific languages fail to be complete despite being part of P. The inquiry seeks clarification on how to demonstrate that these are the only incomplete languages in P. Ultimately, the focus is on the nuances of language completeness in computational theory.
S.ALGH
Messages
3
Reaction score
0
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.
 
Physics news on Phys.org
Then why ø and {0,1} are not complete for P (polynomial) ??
 
What is the context of your question? What subject are you studying? Math or computer science?
 
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 ??
 

Similar threads

Comp Sci What is meant by management of IDN practices resource?
Replies
2
Views
918
Prove or disprove that chop(L) is a regular language
Replies
1
Views
2K
How many words of length n are there in this regular language?
Replies
1
Views
2K
Two computational theory language questions - multi choice
Replies
5
Views
1K
Lingusitics What is the Easiest Spoken Language to Learn?
Replies
25
Views
3K
Book for self-learning calculus and learning in a foreign language?
Replies
41
Views
4K
I Formal language question
Replies
4
Views
1K
Etymology of the word 'fart' in a handful of PIE languages
Replies
4
Views
2K
I Measure with respect to complete measure is also complete
Replies
3
Views
1K
Type of system for programming language based on mathematical set theory
Replies
4
Views
2K

Hot Threads

Recent Insights

Back
Top