-- Apr 17 In-Class Exercise
Let `EXP` be the class of languages decided by deterministic algorithms on inputs of length `n` in time `O(2^{n^k})` for some fixed `k>0`.
Prove `NP\subseteq EXP`. Argue why there is a language not in `EXP`, but can be solved in time `O(2^{2^n})`.
``
Solution: A language `L` belongs to `NP` if there exists a two input polynomial-time algorithm `A` and a constant `c` such that
`L = \{x\in\{0,1\}^*:\exists y, |y| = O(|x|^c) \text{ and } A(x, y) = 1\}`
i.e. it is the class of languages that have polynomial time verification algorithms. To generate all "guesses" for a polynomial verification algorithm, it is exponential on the input, i.e. `O(2^n)`. Therefore, if solving `O(2^n)` size input takes polynomial time, the time for solving all inputs will be `O((2^n)^k) = O(2^{kn})`. This is contained in `O(2^{n^k})`, therefore `NP\subseteq EXP`.
``
Because `O((2^n)^k) = O(2^{kn}) < O(2^{n^k}) < O(2^{2^n})` for some `n` and `k`, there exists some language not in `EXP` but computable in `O(2^{2^n})` time. Imagine that we have a procedure that does the following: it looks at the input and it splits it in different parts, say triples. I.e., `L = \{\langle e, x, 1^t\rangle | t < 2^{n^\log n\} \text{ and } e \text{ is the code of java program s.t. on input x, e runs for less than t steps}\}`. This is not in `EXP` but runs in `O(2^{2^n})` time.
(
Edited: 2019-04-17)
Let @BT@EXP@BT@ be the class of languages decided by deterministic algorithms on inputs of length @BT@n@BT@ in time @BT@O(2^{n^k})@BT@ for some fixed @BT@k>0@BT@.
Prove @BT@NP\subseteq EXP@BT@. Argue why there is a language not in @BT@EXP@BT@, but can be solved in time @BT@O(2^{2^n})@BT@.
@BT@@BT@
'''Solution: ''' A language @BT@L@BT@ belongs to @BT@NP@BT@ if there exists a two input polynomial-time algorithm @BT@A@BT@ and a constant @BT@c@BT@ such that
@BT@L = \{x\in\{0,1\}^*:\exists y, |y| = O(|x|^c) \text{ and } A(x, y) = 1\}@BT@
i.e. it is the class of languages that have polynomial time verification algorithms. To generate all "guesses" for a polynomial verification algorithm, it is exponential on the input, i.e. @BT@O(2^n)@BT@. Therefore, if solving @BT@O(2^n)@BT@ size input takes polynomial time, the time for solving all inputs will be @BT@O((2^n)^k) = O(2^{kn})@BT@. This is contained in @BT@O(2^{n^k})@BT@, therefore @BT@NP\subseteq EXP@BT@.
@BT@@BT@
Because @BT@O((2^n)^k) = O(2^{kn}) < O(2^{n^k}) < O(2^{2^n})@BT@ for some @BT@n@BT@ and @BT@k@BT@, there exists some language not in @BT@EXP@BT@ but computable in @BT@O(2^{2^n})@BT@ time. Imagine that we have a procedure that does the following: it looks at the input and it splits it in different parts, say triples. I.e., @BT@L = \{\langle e, x, 1^t\rangle | t < 2^{n^\log n\} \text{ and } e \text{ is the code of java program s.t. on input x, e runs for less than t steps}\}@BT@. This is not in @BT@EXP@BT@ but runs in @BT@O(2^{2^n})@BT@ time.