We proved Ladner's theorem with a quasi$-$polynomial sized padding of $2^{\sqrt[\phantom{2}]{n}}.$ In this

assignment, you will reprove Ladner's Theorem with a different quasipolynomial padding of

$2^{(log(n{)}^3)}.$ Assume the Exponential Time Hypothesis, that there is no sub exponential time

algorithm for SAT. It cannot be solved by any $2^{o(n)}$ time algorithm. Consider the language:

$L=\{($:$,1^{2^{(log(||{)}^3)}}$:$)|inSAT\}$

Note that the exponent of the padding is not of length $log(log(log(||))),$ but of $(log||{)}^3(5$ points$)$ Prove that $L=($:$,1^{n^3}$:$)$ is NP$-$complete.

$(5$ points$)$ Prove that $L=($:$,1^{2^n}$:$)$ is in P $.$