How can we show that P is not closed under taking all long prefixes?

Question

Let P be the complexity class of languages decidable by Turing machines running in polynomial time. Say a prefix $s$ of a string $x$ is a long prefix (or an L prefix) if $|s|\ge |x|/2$. For a language $A$, let $LP(A)$ be the language of all L prefixes of strings in $A$. Show that $P$ is not closed under $LP(\cdot )$ unless $P=NP$, where NP is the class of languages with polynomial-time verifiers.

I know that for any $A\in NP, LP(A)$ is also in NP. I also know some properties about P, such as the fact that it's closed under complement, intersection, union, and concatenation. But I can't think of a language in P that's not closed under the LP operation. Intuitively, to find such a language, I think it might be useful to construct a language for which it would be very hard to efficiently determine all L prefixes. The resulting language $A$ should most likely satisfy that $LP(A)$ is an NP-complete language. If so, then if $P$ were closed under $LP(\cdot )$, $LP(A)$, an NP-complete language would be in P. Then for any language $B$ in NP, $B\in P.$ Since $NP\subseteq P,$ the result follows.

Alternatively, it might be slightly easier to show that for each $A\in NP,$ we can find some $B\in P$ so that $A\leq_m^p LP(B)$.

Answer 1

In fact Yuval's hint is all the solution you need: consider instance $I$ of any $\mathsf{NP}$-complete problem (e.g. 3SAT) and its proof $c$, let the proof appear in the second half of the constructed language $L$. Then if we can decide whether $I \in \operatorname{LP}(L)$ in poly time, this also means we can decide whether there exists a valid proof $c$ for $I$ in poly time, thus $\mathsf{P} = \mathsf{NP}$.
Formally, construct language $L = \{\left<I, c\right> | \text{$I \in \mathsf{3SAT}$ and $c$ is a valid proof for $I$}\}$. WLOG we can assume $|I| > |c|$ (or we can just use padding trick to ensure this), then $\mathsf{3SAT} \subseteq \operatorname{LP}(L)$. Moreover, by using different encoding alphabet for $I$ and $c$, we can ensure $\mathsf{3SAT} = \operatorname{LP}(L) \cap \Sigma^*$ for some designed $\Sigma$. Thus if $\operatorname{LP}(L) \in \mathsf{P}$, $\mathsf{3SAT} = \operatorname{LP}(L) \cap \Sigma^*$ is also in $\mathsf{P}$, leading to the conclusion that $\mathsf{P} = \mathsf{NP}$.

(This is the first time I answer a question here, please tell me if there are anything unclear. Thank you for tolerance!)

Answer 2

Big hint based on Yuvals Hint: Consider the language $\{\langle S, f \rangle | S \text{ is a SAT formula and } f\text{ a satisfying assingment}\} \in P$