Find a language $L$, such that $L \notin \mathbf{P}$, but $L^* \in \mathbf{P}$ I'm being asked the following


  Find a language $L$, such that $L \notin \mathbf{P}$, but $L^* \in \mathbf{P}$


For the $L \notin \mathbf{P}$-part I have to show that there is no polynomial Turing Machine that could accept $L$. 

I've been struggling with this problem for quite a while, so I would appreciate any help with it.

My attempt:

Let 

$$L = \{0, 1\} \cup \{0^i| M_i\text{ does not accept }\langle M_i \rangle\}$$

Then $L^* = \{0, 1\}^*$. Since this language is regular, we can defined a TM that works on the word $w$ in just a single pass $\implies$ TM runs in $O(|w|) = O(n) \implies L^* \in \mathbf{P}$.

I take this $L$ as example because it seems to me easier to show that $L \notin \mathbf{P}$ by proving that indeed there is no MT that accepts $L$ than showing that it is not accepted by any polynomial MT. To prove the former I was thinking about applying a diagolization argument on $L$.

Am I on the right track? It seems to me that I'm trying to prove something stronger than what I'm asked, so maybe there is a more straightforward way.

Thanks!
Am I on the right track? It seems to me that I'm trying to prove something stronger than what I'm asked


That looks like an excellent approach. Proving something stronger is sometimes easier1 and usually useful.

What's particularly nice about your template for $L$ is that it opens up new questions about what happens if you generalise to $L = A \cup B$ where $A$ and $B$ are in different complexity classes and $B \subset A^*$. The extreme of $A$ regular and $B$ undecidable is good enough, but you could also consider $B \in NP^c$, $B \in EXP^c$, maybe specific context-free $A$, ... Perhaps it would be an interesting question to ask how close they can be to each other while still getting some kind of separation. If you enjoy this kind of thing, there may be a mini research project in it.



1 This is particularly true of proofs by induction, where proving a tight bound often makes the inductive step work where a loose bound wouldn't.