1. Time Complexity (9 points) Let EXP -3SAT = {F #N | F is a satisfiable 3cnf-fo

Question

1. Time Complexity (9 points) 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)
(2) (6points)Show that there is O(n)time algorithm which decides EXP-3SAT wheren=|F#N|=|F|+2|F|.(i.e.,EXP-3SAT P) Hint: There are 2|F | possible assignments of the variables in F . 1. Time Complexity (9 points) 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)
(2) (6points)Show that there is O(n)time algorithm which decides EXP-3SAT wheren=|F#N|=|F|+2|F|.(i.e.,EXP-3SAT P) Hint: There are 2|F | possible assignments of the variables in F . 1. Time Complexity (9 points) 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)
(2) (6points)Show that there is O(n)time algorithm which decides EXP-3SAT wheren=|F#N|=|F|+2|F|.(i.e.,EXP-3SAT P) Hint: There are 2|F | possible assignments of the variables in F .

Explanation / Answer

1)

Given function will get tha all assignments ate <= 2|F, so that F is number of s follwed by exponentital number, but while calculating complexity we can exclude extra coefficients. So time complexity will be O(n) time.

2)

This would be similat to above question that F values will be combination of |F| + 2|F|, so excluding |F| coeffcient value, then possible value assignments are 2|F| on variables F, So running time will be O(n) tiime.

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.