# Proof that $P$ is robust against switching between polynomially equivalent encodings

Lemma 34.1
Let $$Q$$ be an abstract decision problem on an instance set $$I$$, and let $$e_1$$ and $$e_2$$ be polynomially related encodings on $$I$$. Then, $$e_1(Q)\in \mathrm{P}$$ if and only if $$e_2(Q)\in\mathrm{P}$$.

Proof: We need only prove the forward direction, since the backward direction is symmetric. Suppose, therefore, that $$e_1(Q)$$ can be solved in time $$O(n^K)$$ for some constant $$k$$. Further, suppose that for any problem instance $$i$$, the encoding $$e_1(i)$$ can be computed from the encoding $$e_2(i)$$ in time $$O(n^c)$$ for some constant $$c$$, where $$n=|e_2(i)|$$. To solve problem $$e_2(Q)$$, on input $$e_2(i)$$, we first compute $$e_1(i)$$ and then run the algorithm for $$e_1(Q)$$ on $$e_1(i)$$. How long does this take? Converting encodings takes time $$O(n^c)$$ and therefore $$|e_1(i)|=O(n^c)$$, since the output of a serial computer cannot be longer than its running time. Solving the problem on $$e_1(i)$$ takes time $$O(|e_1(i)|^k) = O(n^{ck})$$, which is polynomial since both $$c$$ and $$k$$ are constants. $$\blacksquare$$

I have some questions to the proof:

1. Why does it only consider $$e(i)$$? As I know, $$Q$$ is binary relation on the set of instances $$I$$ and the set of solution so if we say that $$e(Q)$$ and it should be $$e(i,s)$$.

Let $$Q$$ be an abstract decision problem: What is an instance of NP complete problem?

1. The proof only shows the forward direction.

Step 1. suppose that $$e_1(Q)$$ can be solved in polynomial time

Step 2. convert $$e_2(i)$$ into $$e_1(i)$$ to prove $$e_2(Q)$$ can be solved in polynomial time.

If we prove the backward direction, then we can confirm $$e_1(Q)$$ to be solved in polynomial time as well, am I right?

• I converted your images to text so they're searchable. Please let us know which book the theorem and its proof came from: we should acknowledge its source. It might also help if you gave the definition of "polynomially related encodings" since it's not one I'm familiar with, even though I work with algorithms and complexity. – David Richerby Jul 31 '15 at 16:19
• The reason only one direction of the proof is given is that the other direction is absolutely identical, except for switching "1" to "2" and vice-versa. (You'd get different constants $k$ and $c$, too, so you would probably call them $k_1$, $k_2$, $c_1$ and $c_2$.) – David Richerby Jul 31 '15 at 16:21
• What book/reference is this lemma from? – Ryan Jul 31 '15 at 17:28
• I use Introduction to Algorithms, third edition (By Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein) – Y.S. Chen Aug 1 '15 at 1:03
• $Q$ is a unary relation on the set of instances, i.e., a subset of the set of instances. – Yuval Filmus Aug 2 '15 at 21:32