2
$\begingroup$

I tried using the padding argument to prove such a thing (as it appeared in Arora's book), but I am not sure how this technique will help me here. I am trying to get to a contradiction to the Time Hierarchy Theorem.

After the assumption, I want to prove that $\mathsf{NP} = \mathsf{DTIME}(2^{n})$.

The first case $\mathsf{NP} \subset \mathsf{DTIME}(2^{n})$, is trivial.

For the second case, let $L \in \mathsf{DTIME}(2^{n})$ and $M$ be a deterministic TM that can decide it, let $$L_{\mathrm{pad}} = \left\{\left\langle x,1^{2^{\sqrt{|x|}}} \right\rangle : x \in L\right\}.$$ I am not sure how, using $L_{\mathrm{pad}}$, I can reach a conclusion that $\mathsf{NP} = \mathsf{DTIME}(2^{n})$, I feel like I am missing something and that my method is not in the right direction, or it is lacking an extra detail.

Improve this question
$\endgroup$
  • $\begingroup$ This is a very odd question. We know that $DTIME(2^{\sqrt{n}})\neq DTIME(2^n)$, from the time hierarchy theorem. So you're basically asking to prove that $NP\neq DTIME(2^{\sqrt{n}})$? $\endgroup$ – Shaull Jan 1 '20 at 19:58
  • $\begingroup$ @Shaull Yes indeed, I was thinking about contradicting the time hierarchy theorem and reach a conclusion that my initial assumption was wrong, hence $NP \neq DTIME(2^{\sqrt{n}})$, I tried proving it by constructing a langue in NP but not in the other one, or the opposite, but I couldn't come up with anything. $\endgroup$ – user574362 Jan 1 '20 at 20:33
  • $\begingroup$ Try padding only $|x|^2$ 1's. $\endgroup$ – xskxzr Jan 2 '20 at 3:02
  • $\begingroup$ @xskxzr How will this help me, can you explain your intuition? $\endgroup$ – user574362 Jan 2 '20 at 6:53
1
$\begingroup$

It is enough to pad a special delimiter (say a comma) and $(|x|^2-|x|-1)$ 1's. Suppose $L_\mathrm{pad}= \left\{\left\langle x,1^{|x|^2-|x|-1} \right\rangle : x \in L\right\}$. Since $L\in\mathsf{DTIME}(2^n)$, there is a TM that can determine whether $x\in L$ in $O(2^{|x|})$ time. We then construct a new TM: given a string $y$, it first checks whether $y$ has the form $\left\langle x,1^{|x|^2-|x|-1} \right\rangle$, then simulates $M$ on $x$. This new TM determines whether $y\in L_\mathrm{pad}$ in $O(2^{|x|})=O\left(2^{\sqrt{|y|}}\right)$ time, so we have $L_{\mathrm{pad}}\in \mathsf{DTIME}\left(2^{\sqrt{n}}\right)$, thus $L_{\mathrm{pad}}\in\mathsf{NP}$ by your assumption. This means there exists a non-deterministic TM $M'$ that decides $L_{\mathrm{pad}}$ in polynomial time. Hence, we can construct a new non-deterministic polynomial-time TM that decides $L$ by first padding a comma and $(|x|^2-|x|-1)$ 1's to the input then simulating $M'$, which means $L\in\mathsf{NP}$.

Improve this answer
$\endgroup$

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.