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

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)$$.

• The idea is for the witness to appear in the second half. Jul 21, 2022 at 22:03
• @YuvalFilmus thanks. Could you elaborate? Jul 22, 2022 at 2:47
• It’s a hint. You need to flesh it out. Jul 22, 2022 at 4:40
• The problem: If I give you a string S, you'd have to find a string T with a length from S to 2S such that S is in L, or prove that one exists, in polynomial time. Aug 24, 2022 at 13:52

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 | \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}$$.
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$$