1. Given that the algorithm to determine the output of some input takes polynomial time, it will take n^k amount of time for size n and some fixed k. Generating all combinations of outputs would thus take O(2^(nk)), which is contained in O(2^(n^k)). As NP is a class of languages that have polynomial time verification. Find a language that has a deterministic algorithm for verification that runs in O(2^kn) and has an exponential amount of inputs. and it will require O(2^(n^k)).

When a language L is NP where L={x∈{0,1}⋆:∃y,|y|=O(|x|c)

A(x, y) = 1

NP is in EXP since NP: |y| = O(|x|^c) < EXP: |y| = O(2^(|x|^k)). L = {<e, x, 1^t> | t < 2^(n^(log n)) So L is not in EXP since can only be solved in O(2^2^n)

1. With the L belonging to NP if there exists a two input polynomial-time algorithm A and a constant c such that, L={x∈{0,1}⋆:∃y,∣∣y∣∣=O(∣∣x∣∣c) and A(x,y)=1}. Generating all combinations would take O(2^(nk)) which is less time than O(2^n^k), thus NP⊆EXP.

A language L belongs to NP if there exists a two input polynomial-time algorithm A and a constant c such that L={x∈{0,1}⋅:∃y,|y|=O(|x|c) and A(x,y)=1} i.e. it is the class of languages that have polynomial time verification algorithms. To generate all combinations 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^nk), therefore NP⊆EXP.

If a language L belongs to NP then there exists a two-input p-time algorithm A and constant c such that L={x∈{0,1}*:∃y,|y|=O(|x|^c) and A(x,y)=1}. For an input of length n, it takes O(2^n) time to get all the guesses for polynomial verification algorithm. For all k many inputs, it takes O((2^n)^k) = O(2^(nk)), since nk <= n^k, therefore 2^(nk) <= 2^(n^k) or NP⊆EXP. L={⟨e,x,1^t⟩∣t<2^n^logn and e is the code of java program such that on input x, e runs for less than t steps} . This is not in EXP but runs in O(2^2^n) time.