Question

Prove that if$\mathbf{NEXPTIME}\mathbf{\ne }\mathbf{EXPTIME}$, then $\mathbf{P}\mathbf{\ne }\mathbf{NP}$. You may find the function pad, defined in problem 9.13, to be helpful.

Short answer

If$\mathbf{NEXPTIME}\mathbf{\ne }\mathbf{EXPTIME}$, then$\mathbf{P}\mathbf{\ne }\mathbf{NP}$proved by taking its contrapositive i.e., If $\mathbf{P}\mathbf{=}\mathbf{NP}$then $\mathbf{NEXPTIME}\mathbf{\ne }\mathbf{EXPTIME}$,

Step-by-step solution

Assuming  and proving the contrapositive

If$\mathbf{L}\mathbf{\in }\mathbf{}\mathbf{NTIME}\left(2^{2^{°}}\right)$ then the language${\mathbf{L}}_{\mathbf{pad}}\mathbf{=}\left\{<x,1^{2\left|x\right|°}>:x\in L\right\}$ is in NP. This process of adding a string of symbols to each string in the language is known as padding.

So, if $\mathbf{P}\mathbf{=}\mathbf{NP}$then${\mathbf{L}}_{\mathbf{pad}}$ is in P but if ${\mathbf{L}}_{\mathbf{pad}}$ is in P then L is in EXPTIME.

Using the polynomial-time machine

In order to conclude whether an input x is in L, it just pads the input and decides whether it is in${\mathbf{L}}_{\mathbf{pad}}$ (Using polynomial-time machine for)

Hence, we can say that if $\mathbf{P}\mathbf{=}\mathbf{NP}$ is assumed then NEXPTIME =EXPTIME and so it can also be said that if $\mathbf{NEXPTIME}\mathbf{\ne }\mathbf{EXPTIME}$, then $\mathbf{P}\mathbf{\ne }\mathbf{NP}$.