edited by
1,211 views
4 votes
4 votes

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 by

3 Answers

0 votes
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 by
0 votes
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
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
2 votes
1 answer
1
val_pro20 asked May 11, 2019
2,601 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)$ Rep...
4 votes
4 votes
4 answers
2
vupadhayayx86 asked May 2, 2019
1,349 views
Simplify the following expressionAB’C + A’BC + A’B’CSolution given is A’C + B’C can someone show me how?
1 votes
1 votes
0 answers
4