Are all $\mathbf{P}$ languages $\mathbf{P}$-complete with respect to polynomial-time reduction?

Question

Question: Is language $L \in \mathbf{P}$ also $\mathbf{P}$-complete with respect to polynomial-time reduction?

My thoughts: Given a language $L \in \mathbf{P}$, we want to show that for any other language $L' \in \mathbf{P}: L' \leq_p L$. To do this, given any input $w' \in \Sigma^*$, we can check in polynomial time if $w' \in L'$. If:

• $w' \in L'$: construct a word $w \in L$.
• $w' \notin L'$: construct a word $w \notin L$.

This construction would satisfy the existence of $f\colon \Sigma^* \to \Sigma^*, w' \in L' \iff f(w') \in L$.

This is where I stuck: Given a language $L$, how can we find a word $w \in L$ or a word $w \notin L$.

Addendum: I think I understood the problem. Since $L' \leq_p L$ only requires existence of $f\colon \Sigma^* \to \Sigma^*$, I don't need construct $f$.

Answer 1

I think you almost got it right, here is what you are missing: if $L$ is not trivial (i.e, not empty and not $\Sigma^*$) then there are words $w_1\in L,w_2\notin L$. You can use them to construct $f$.