1
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ You can prove that $L$ (or a similar language) is not computable by reduction from the halting problem. $\endgroup$ – Yuval Filmus Feb 18 at 17:18
  • $\begingroup$ @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. $\endgroup$ – Jazz Feb 18 at 23:07
  • $\begingroup$ You can make $M$ independent of its input, for example. $\endgroup$ – Yuval Filmus Feb 19 at 2:08
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.