I am trying to show that $L^* \in P $ does not necessarily mean that $L \in P$. My idea was to find a language $L \notin P$ , apply $*$ operator and show that $L^* \in P$ by showing that $L^*$ can be decided with a polynomially bounded Turing machine, which will be a contradiction to $L^* \in P \Rightarrow L \in P$. However, I am having trouble in finding such $L$. Is there a trivial $L$ that I'm not thinking of? Or should change my method? Any help will be appreciated.

  • 1
    $\begingroup$ The method is ok. A hint: what about unary languages? What happens if $\{1\}$ is included in an unary language? $\endgroup$ – Vor May 17 '17 at 12:00

Yes, your method is fine and, yes, there's a fairly trivial way to complete your proof attempt: it's easy to arrange that $L^*=\Sigma^*$, which is in P.

| cite | improve this answer | |

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.