Please post your solutions to the Apr 17 In-class Exercise to this thread.

Best,

Chris

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.

Assuming the language is of the form defined by NP (L={x∈{0,1}:∃y,|y|=O(|x|c) and A(x,y)=1}). Language E is the class of languages given by checking to see if the string equates to a particular predefined string (password). This runs in O(2^(n^k)) to calculate. This shows that NP is contained in EXP.

There exists an algorithm that tests the truth of the resulting of the algorithm that determines if the result is the password. This language is not in EXP but can be solved in O(2^2^n).

`Let EXP be the class of languages decided by deterministic algorithms on inputs of length n in time O(2nk) for some fixed constant k>0.

Prove NP⊆EXP. Argue there is a language not in EXP, but which can be solved in time O(22n).`

Solution:

L={x∈{0,1}:∃y,y=O(xc) and A(x,y)=1}

L={<e,x,1^t>} | <2^n^logn& e is the code of java program s.t. On input x, e runs for less than t steps}

We show that L above not in x, therefore there is a language not in EXP but which can be solved in time O(2^2^n)

EXP = {x in {0, 1}* : there is a y, |y| = O(2^(|x|^k)) and A(x, y) = 1}

NP is in EXP as NP has |y| = O(|x|^c) which is less than EXP's |y| = O(2^(|x|^k)).

L = {<e, x, 1^t> | t < 2^(n^(log n)) and e is the code of java program s.t. on input x, e runs for less than t steps}

1.NP is a class of languages that have polynomial time verification.

E is a class of languages that have deterministic algorithms that run in O(2^kn).

NP is contained in E. For any NP language, we can determine membership in O(2^kn) by generating all 2^n guesses for y and verifying a guess in polynomial time. Verifying all guesses would take exponential time which is O(2^kn).

1. Argue there is a language not in E, but which can be solved in time O(2^2^n).

Another form of this problem is that there is a language in 2 EXPTIME but not in EXPTIME. Find a language that has a deterministic algorithm for verification that runs in O(2^kn) and has an exponential amount of inputs. To test all inputs, it would require O(2^2^kn).

1. Prove NP⊆EXP

For a language L belong to NP, we know L={x∈{0,1}:∃y,|y|=O(|x|^c) and A(x,y)=1}, where we have input length of O(n^k). For a language L' belong to EXP, we know L'={x∈{0,1}:∃y,|y|=O(2^(|x|^k)) and A(x,y)=1}, where we have input length of O(2^(n^k)). Since O(n^k) < O(2^(n^k)), we know NP⊆EXP.

1. Argue there is a language not in EXP, but which can be solved in time O(2^(2^n)).

We know O(n^k) < O(2^n), then, O(2^(n^k)) < O(2^(2^n)). For a language L with input length O(2^(2^n)), it is not in EXP but it can be solve in O(2^(2^n)).

A language L belongs to NP is 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}. There are 2^(|x|^c) = 2^(n^c)guesses in total. L' belongs to EXP, L' = {x∈{0,1} : ∃y,|y|=O(2^|x|^k ) and A(x,y)=1} If for all guesses of L, A(x, y) = 0, then reject x. For each guess, it verifies it in polynomial time. For all guesses, the total time to verify it is less than O(2^|x|^k).Therefore, NP is a subset of EXP. For L={e,x,1^tt<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.

1. A language L is in NP if there exists a 2 input polynomial time algorithm A and constant c s.t.

L= {x in {0,1}^star : exists y, |y| = O(|x|^c) mbox( and ) A(x,y)=1}

Run A(x,y) and see if it outputs 1 for each y. To generate 1 guess takes polynomial time. To cycle through all guesses takes exponential time. If the algorithm never outputs 1 after going through all strings of quadratic length, output 0. The time this takes is < 2^{n^k}, showing that NP subseteq EXP.

1. L is a fixed concrete language such that:

L = {<e,x,1^t> | t < 2^{nlogn} & e is the code of any java program s.t. on input x, runs for < t steps}

This procedure looks at input and splits it into different parts, say triples. 2^{n^logn} will eventually be bigger than 2^{n^k} as n gets big. If L were in EXP, there would be some Java program.

L can be decided in O(2^{2^n}) but not O(2^{n^k}).

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)).