[Solved]: Space(n) not closed under Karp reductions - what about NTime(n)?

Problem Detail: 

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?

Asked By : G. Bach

Answered By : Yuval Filmus

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/12702

 Ask a Question

 Download Related Notes/Documents