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?

  • 4
    $\begingroup$ 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. $\endgroup$ – David Richerby Jul 31 '15 at 16:19
  • 2
    $\begingroup$ 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$.) $\endgroup$ – David Richerby Jul 31 '15 at 16:21
  • 1
    $\begingroup$ What book/reference is this lemma from? $\endgroup$ – Ryan Jul 31 '15 at 17:28
  • $\begingroup$ I use Introduction to Algorithms, third edition (By Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein) $\endgroup$ – Y.S. Chen Aug 1 '15 at 1:03
  • 2
    $\begingroup$ $Q$ is a unary relation on the set of instances, i.e., a subset of the set of instances. $\endgroup$ – Yuval Filmus Aug 2 '15 at 21:32

Your Answer

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

Browse other questions tagged or ask your own question.