# GateBook Test Series: Digital Logic - Boolean Algebra

4 votes
417 views

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)$?

1. $O(2^n)$
2. $O(g(n))$ where $g$ is a polynomial
3. $O(log(n))$
4. None of the above

edited
0
.Yes it is B
0
is it option D ?
0
Answer is B
3

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

## 3 Answers

0 votes
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.

edited
0
could you please explain more
0
Answer is b
1
The question is a bit unclear so I interpreted it as :

To check whether there exists an assignment such that the formula is true, this requires computing all possible assignments , there are $2^n$ of them. It'd be $O(2^n)$.
On the other hand 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$
0
Look at my next comment, i hope it'd be clear now. Let me modify the answer as well.
0
to check whether assigning a true value to each ---why you are considering by own.In question  it is not mention right ?
0
Yes that was my mistake. I've edited now.
0 votes
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.
0 votes

Answer : B

its 2-SAT problem

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

## Related questions

2 votes
1 answer
1
273 views
$(a) A = 101010$ and $B = 011101$ are $1’s$ complement numbers. Perform the following operations and indicate whether overflow occurs. $(i) A + B$ $(ii) A − B$ $(b)$ Repeat part $(a)$ assuming the numbers are $2’s$ complement numbers.
2 votes
4 answers
2
310 views
Simplify the following expression AB’C + A’BC + A’B’C Solution given is A’C + B’C can someone show me how?
1 vote
0 answers
3
138 views
which of the following subtraction operations will result in F16? (BA)16 - (AB)16 (BC)16 - (CB)16 (CB)16 - (BC)16 Select the correct answer using the code given below: A. only 2 and 3 B. only 1 and 2 C. 3, 1 and 2 D. only 1 and 3
5 votes
1 answer
4
195 views
The maximum number of Boolean expressions that can be formed for the function f(x, y, z) satisfying the relation is ___________.