Digital - Boolean Algebra - 11

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
reshown May 14

+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-

TO KNOW ABOUT NP-COMPLETE- answered May 14 by (1,950 points)
I am not sure of this answer, I would request gatebook to give solution to this problem!
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
@getgatebook

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 (11,660 points)
I agree. @getgatebook - please provide explanation from your end

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 (340 points)
edited Jun 24 answered Aug 4 by (10,380 points)