Digital - Boolean Algebra - 11

+8 votes
What is the time complexity for checking whether an assignment of truth values 
to variables x1 … xn satisfies a given formula f(x1,...,xn)?

(A) O(2^n)
(B) O(g(n)) where g is a polynomial
(C) O(log(n))
(D) None of the above
asked May 12 in Digital by getgatebook (31,410 points)
reshown May 14 by getgatebook

5 Answers

+1 vote
In my opinion, the answer should be D, none of the above.

This question is of type- BOOLEAN SATISFIABILITY PROBLEM. It is NP-complete problem meaning, it has non-deterministic polynomial time complexity.

If it was given that the formula is of CNF form, then yes, the problem was P-class, and the problem is called 2-SAT problem and complexity would be polynomial time. But, it isn't mentioned like that in the question, so I don't know if we should assume or not.

For more reference as to what is 2-SAT and SAT problem-


answered May 14 by tssarvajitsankar (1,950 points)
I am not sure of this answer, I would request gatebook to give solution to this problem!
+7 votes
It's option B.

The problem, correctly, is NP complete. NP complete things cannot be solved in polynomial time but a given solution can be verified in polynomial time (and that's what this question asks).
answered May 14 by (660 points)
how does np complete problem can be reduced to np or p problem can u explain
same doubt i have in options its given B here explanation for D is given
+1 vote

Please provide explanation for this question as soon as possible and if this question is related to NP-P problem as answered  by some users why such question are given in the exams as this topic is removed from the syllabus.
answered May 14 by tskushagra-guptacse (11,660 points)
I agree. @getgatebook - please provide explanation from your end
+3 votes

Lets take a boolean function f(A,B)=A+B of 2 boolen variables.

A     B        A+B

0      0        0

0      1        1

1      0        1

1      1        1

Suppose we have to find out any A,B combination for which f(A,B) gives value 1, to do so we might have check all (2n=22=4) conbinations for which f(A,B) may give value 1.

But for a given combination(A,B) if we have to check whether the functional output is 1 or not we can easily do that in polynomial time. Hence option (B)

So as we can't find out solution of such given problem in polynomial time but given a solution we can always verify in polynomial time,so this problem falls under NP category.

answered Jun 24 by himansahapro20 (340 points)
edited Jun 24 by himansahapro20
0 votes
Ans should be D. Gatebook official please clarify this.

We have given n variables and so 2^n combinations possible and each combination of n lenght.

So time complexity of each combination is n which is polynomial and multiply by 2^n for all.

Therefore time complexity = (n*2^n) which is not polynomial in nature.

Hence D
answered Aug 4 by bhargavakapilpro20 (10,380 points)