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

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!

• You can prove that $L$ (or a similar language) is not computable by reduction from the halting problem. – Yuval Filmus Feb 18 '19 at 17:18
• @YuvalFilmus when we reduce a language $A$ to a language $B$, we take an instance $x$ of A and transform it into an instance $f(x)$ of $B$ so that $x \in A$ iff $f(x) \in B$. I cannot see how $M$ halting on $w$ would mean (can be transformed such that) that $M$ doesn't accept its own description. I'd appreciate any hint. – Jazz Feb 18 '19 at 23:07
• You can make $M$ independent of its input, for example. – Yuval Filmus Feb 19 '19 at 2:08

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.