Pergunta

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!

Nenhuma solução correta

Licenciado em: CC-BY-SA com atribuição
Não afiliado a cs.stackexchange
scroll top