1

This is an interesting question I'm stuck with:

Define a relabelling to be a function $\phi : \Sigma \to \Sigma$ (not necessarily a bijection).

If $x = x_1 \ldots. x_n$ is a string, we define $\varphi(x) = \varphi(x_1)φ=\varphi(x_2) \ldots \varphi(x_n)$.

If $L$ is a language, we define $\varphi(L) = \{\varphi(x) : x \in L\}$.

Show that if a language $L$ is in NP, and $\varphi$ is a relabelling, then $\varphi(L) \in \text{NP}$.

Thanks in advance!

Community
  • 1
  • 1
    Take a Turing machine for $L$ and relabel its transition arrows with $\varphi$ to obtain a Turing machine for $\varphi(L)$. – Hagen von Eitzen Apr 19 '17 at 20:34
  • 1
    @HagenvonEitzen I like that approach. Note it could turn a deterministic TM into a nondeterministic TM, so it doesn't show that $\text{P}$ is closed under relabeling -- only that $\text{NP}$ is. (In fact, it is possible that $L \in \text{P}$ but $\varphi(L) \notin \text{P}$.) – Caleb Stanford Apr 19 '17 at 20:38
  • Could it be shown that if P is closed under relabelling then P = NP? –  Apr 19 '17 at 23:36
  • 1
    @bistables Yes, I should have been more careful in my earlier statement. What I mean is it's possible that $L \in \text{P}$ but $\varphi(L)$ is NP-complete. [To see this take $L$ to be the collection of boolean formulas followed by a list of assignments ($0$ or $1$) to all the variables, and then take $\varphi$ so that $\varphi(1) = \varphi(0) = 0$. Then $\varphi(L)$ is the SAT problem.] Therefore, if P is closed under relabelling then P = NP. – Caleb Stanford Apr 20 '17 at 01:56
  • I don't quite understand what L is here, and how it belongs to P? –  Apr 20 '17 at 10:48
  • I also don't understand how φ(L) is the SAT problem. –  Apr 20 '17 at 11:10
  • @bistables If you have seen the SAT problem, what I meant is that a string in $L$ consists of a formula $\varphi$ followed by a satisfying assignment to that formula. For example, one element of $L$ is $\langle(x_1 \lor x_2 \lor x_3) \land (x_2 \lor x_4), 0, 1, 0, 0\rangle$ because $x_1 = 0$, $x_2 = 1$, $x_3 = 0$, and $x_4 = 0$ satisfies the formula. – Caleb Stanford Apr 20 '17 at 18:22
  • If you take $\phi$ of that string, assuming that $0$ and $1$ are not used except in writing down the satisfying assignment, you get $\langle (x_1 \lor x_2 \lor x_3) \land (x_2 \lor x_4), 0, 0, 0, 0\rangle$. So $\phi(L)$ is the set of satisfiable formulas followed by a string of $0$s. The string of $0$s does not help at all, so deciding $\phi(L)$ is just deciding SAT. – Caleb Stanford Apr 20 '17 at 18:24
  • Anyway if that's confusing don't worry about it -- it would take a bit of work on your part to prove carefully that everything I said is true (namely that $L$ is in P and $\phi(L)$ is NP-complete for this $L$, and to fill in all the details). I just mean to point out that this re-labelling option might turn something in P into being NP-complete. – Caleb Stanford Apr 20 '17 at 18:26
  • By the way I don't get a notification unless you ping me with @6005 so I wouldn't have seen your comments. – Caleb Stanford Apr 20 '17 at 18:27
  • 1
    @6005 Thanks! All of that is useful! –  Apr 20 '17 at 18:29

1 Answers1

0

Here is one way to do it:

Let $M$ be a nondeterministic poly-time Turing machine for $L$; we build a nondeterministic poly-time Turing machine $N$ for $\varphi(L)$:

  • On input $y = y_1 y_2 \ldots y_n$, first nondeterministically guess the original string $x = x_1 x_2 \ldots x_n$. First, check if $\varphi(x_1) \varphi(x_2) \ldots \varphi(x_n) = y_1 y_2 y_3 \ldots y_n$; if not, immediately reject. If so, run $M$ on $x$.

Can you explain why this works?

Caleb Stanford
  • 45,895
  • So this basically tries every possible string until it either accepts or runs out of possibilites? And we can be sure it runs in polynomial time because each separate branch of computation does? –  Apr 19 '17 at 21:53
  • 1
    @bistables Yes, it is trying all possible strings at once that $y$ could be a "relabelling" of. And yes, in each particular branch you just have to write down $x$ (which has length $n$) and then run $M$ (which runs in polytime), so the total is also polytime. Let me know if you have any other questions. – Caleb Stanford Apr 20 '17 at 02:00
  • 1
    @jd123 $\varphi(L)$ might be NP-complete, but it also might not (for example if $\varphi$ is a bijection, it won't be NP-complete). For an example where it is NP-complete, see my comment exchange on the question. – Caleb Stanford Apr 21 '17 at 09:02