GateBook Test Series: Digital Logic - Boolean Algebra

Question

What is the time complexity for checking whether an assignment of truth values to variables $x_1,\dots ,x_n$ satisfies a given formula $f(x_1\dots,x_n)$?

• A. $O(2^n)$
• B. $O(g(n))$ where $g$ is a polynomial
• C. $O(log(n))$
• D. None of the above

Comments

.Yes it is B

---

is it option D ?

---

Answer is B

---

This problem is Boolean satisfiablility problem (SAT) and SAT problem is proven to be NP Complete by Cook's theorem. That means it is solvable in Non-deterministic polynomial time. So, option B is correct. Please refer below links for better understanding:

https://www.geeksforgeeks.org/2-satisfiability-2-sat-problem/

https://en.wikipedia.org/wiki/Boolean_satisfiability_problem

https://en.wikipedia.org/wiki/Cook%E2%80%93Levin_theorem

 

Answer 1

If i'd have to check whether assigning a true value to each of $x_1,x_2,....x_n$ satisfies the formula or not can be done in polynomial time. i.e option B.

Comments

Look at my next comment, i hope it'd be clear now. Let me modify the answer as well.

---

to check whether assigning a true value to each ---why you are considering by own.In question  it is not mention right ?

---

Yes that was my mistake. I've edited now.

Answer 2

Since , the formula is given , we are to check whether assignment of truth value to all the variables satisfies the formula , this can be done in polynomial time. i.e Option B.

Answer 3

Answer : B

its 2-SAT problem

2-SAT is a special case of Boolean Satisfiability Problem and can be solved
in polynomial time.