Let EXP-3SAT={F#^N| F is a satisfiable 3cnf-formula and N = 2^|F| } (i.e.,F is a formula followed by an exponential number of #s)

(1) (3 points) Which of the following are instances of EXP-3SAT? Justify why or why not.

(x₁x₂(not)x₂)#^{2^7}

(x₁x₂(not)x₂)#

(x₁x₁x₁)((not)x₁(not)x₁(not)x₁)#^{2^15}

(2) (6 points) Show that there is O(|F|n) time algorithm which decides EXP-3SAT where n=|F#^N|=|F|+ 2^|F|. (i.e.,EXP-3SATP)

Hint:There are 2^|F| possible assignments of the variables in F

Let EXP-3 SAT F #N l F is a satisfiable 3cnf formula and N Fl) (i.e., F is a formula followed by an exponential number of #s) (1) (3 points) Which of the following are instances of EXP-3SAT? Justify why or why not. 27 15 (2) (6 points) Show that there is O (IFIn) time algorithm which decides EXP-3SAT Where n F#N FI 2 Fl. (i.e., EXP-3 SATE P Hint 1: There are 2 possible assignments of the variables in F Let EXP-3 SAT F #N l F is a satisfiable 3cnf formula and N Fl) (i.e., F is a formula followed by an exponential number of #s) (1) (3 points) Which of the following are instances of EXP-3SAT? Justify why or why not. 27 15 (2) (6 points) Show that there is O (IFIn) time algorithm which decides EXP-3SAT Where n F#N FI 2 Fl. (i.e., EXP-3 SATE P Hint 1: There are 2 possible assignments of the variables in F