In the book on complexity by Arora and Barak, there is an exercise to show $Space(n)\neq NP$, the proof of which goes by showing that $NP$ is closed under Karp reductions, while $Space(n)$ isn't.

To show that $Space(n)$ isn't closed under Karp reductions, the suggested technique (both in the solutions given at my place of study as well as those given at many other universities) is to assume we have a TM that decides language $L$ in $Space(n^2)$. Now take an encoding $enc(x)$ of some $x$ in $L$ with $|enc(x)| = n$ and blow it up (in quadratic, thus polynomial time) to an encoding $enc'(x)$ of $x$ with $|enc'(x)| = n^2$ by padding the smaller encoding with $n^2-n$ padding symbols. Now we take the same TM, and it can decide $L$ in space linear in $enc'(x)$ by ignoring the padding stuff and just operating on $enc(x)$. This implies that $Space(n^2) \subseteq Space(n)$, which contradicts the space hierarchy theorem, so $Space(n)$ can't be closed under Karp reductions.

My problem here is that while I realize that we can easily show that $NP$ is closed under Karp reductions, it somewhat confuses me regarding what this says about $NTime(s(n))$. It seems to me that this approach will also work to show that $NTime(s(n))$ isn't closed under Karp reductions for any time-constructible function s(n) using the time hierarchy theorem, or am I mistaken here?


You're not mistaken. The reason NP is different is that it's defined as the union of $NTime(n^k)$ for all $k \geq 0$, so the set of upper bounds on the running time $s(n)$ is closed under substituting polynomials.

| cite | improve this answer | |
  • $\begingroup$ Thanks, I was worried I might have misunderstood something, so hearing from someone else that I was right was all I needed :) $\endgroup$ – G. Bach Jun 17 '13 at 1:02

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.