# A tricky P=NP problem

Define an operator $$\pi(\cdot)$$: for a language $$L$$, $$\pi (L)$$ is the set of all prefixes of strings in $$L$$ with length at least half of the original string. Prove that if $$\mathsf{P}$$ is closed under $$\pi$$ we have $$\mathsf{P}=\mathsf{NP}$$.

This is a homework question I had. My current sketch is: for a language $$L_1 \in \mathsf{NP}$$, define another language $$L_2\in \mathsf{P}$$ based on $$L_1$$ such that deciding $$\pi(L_2)$$ helps decide $$L_1$$. Here $$\pi(L_2)$$ is decidable as $$\mathsf{P}$$ is closed under $$\pi(\cdot)$$; $$L_1$$ being decidable infers that $$L_1\in \mathsf{P}$$ and thus $$\mathsf{P}=\mathsf{NP}$$.

I think my sketch is in the right direction but I'm struggling in defining the appropriate $$L_2$$ here. Any hint would be appreciated!

• I don't see a question here. This is a question-and-answer site, so we require you to articulate a specific question in your post. Also, we discourage posts that are just the statement of an exercise-style problem, with no context or motivation. Instead, you should ask a question about the exercise. See cs.meta.stackexchange.com/q/1284. Also, please identify the original source where you encountered this problem. – D.W. Apr 7 '19 at 5:36
• @D.W. Thank you. I just rephrased my question and added supplement information. – jsantp Apr 7 '19 at 6:27
• Please credit the original source where you encountered this problem. You always need to provide a full reference for the original source for all copied material. – D.W. Apr 7 '19 at 15:41