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!

  • 2
    $\begingroup$ 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. $\endgroup$ – D.W. Apr 7 '19 at 5:36
  • $\begingroup$ @D.W. Thank you. I just rephrased my question and added supplement information. $\endgroup$ – jsantp Apr 7 '19 at 6:27
  • $\begingroup$ 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. $\endgroup$ – D.W. Apr 7 '19 at 15:41

You are asked to prove: There is a language X which is in P, such that the language π(X) is NP complete. Because in this case, since P is closed under the operation π, π(X) is also in P, which means P = NP. The idea is: Define a language X, which consists of strings that are YES-instances of an NP-complete problem, followed by an oracle that proves the instance is a YES-instance. The details are a bit tricky.

Define an encoding of instances of the travelling salesman problem: The encoding starts with the number n of cities in decimal notation, a comma, the number K which is the maximum length of a tour, an opening bracket, n * (n-1) / 2 distances in decimal notation, separated by commas if there is more than one distance, and a closing bracket. It is easy to determine that a string is such an encoding of a TSP instance.

We define the language L as follows: Each string in L consists of the encoding of a TSP instance with answer "YES", followed by hyphen characters "-" to exactly double the length of the string so far, followed by a permutation of the numbers 1 to n in decimal notation, separated by commas, such that starting at town 1, then visiting towns in the given order, produces a cyclic tour with length at most K.

The language L is clearly in P. The language π(L) consists of strings that are the encoding of a YES-instance of TSP, followed by some number of hyphens, and if there are enough hyphens, part or whole of an oracle. Because the oracle is much shorter than the encoded instance, π(L) contains some strings that are just encoded TSP instances, followed by hyphens. But for these strings, deciding that they are in π(L) is hard, as hard as deciding that an ordinary instance of TSP is a YES-instance. So π(L) is NP-complete.

And if π(L) is also in P as assumed, then P = NP.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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