2
$\begingroup$

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

$\endgroup$
4
  • 1
    $\begingroup$ The idea is for the witness to appear in the second half. $\endgroup$ Commented Jul 21, 2022 at 22:03
  • $\begingroup$ @YuvalFilmus thanks. Could you elaborate? $\endgroup$ Commented Jul 22, 2022 at 2:47
  • $\begingroup$ It’s a hint. You need to flesh it out. $\endgroup$ Commented Jul 22, 2022 at 4:40
  • $\begingroup$ 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. $\endgroup$
    – gnasher729
    Commented Aug 24, 2022 at 13:52

2 Answers 2

1
$\begingroup$

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!)

$\endgroup$
0
$\begingroup$

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$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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