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)$? $O(2^n)$ $O(g(n))$ where $g$ is a polynomial $O(log(n))$ None of the above Digital Logic gatebook digital-logic boolean-algebra + – val_pro20 asked May 15, 2019 • edited May 28, 2019 by akash.dinkar12 val_pro20 1.3k views answer comment Share Follow See all 4 Comments See all 4 4 Comments reply Satbir commented May 25, 2019 i edited by Satbir Oct 4, 2019 reply Follow Share .Yes it is B 0 votes 0 votes Satbir commented May 25, 2019 reply Follow Share is it option D ? 0 votes 0 votes Gateasp2020 commented May 27, 2019 reply Follow Share Answer is B 0 votes 0 votes APOORV PANSE commented Jun 29, 2019 reply Follow Share 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 votes 3 votes Please log in or register to add a comment.
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. Arkaprava answered May 15, 2019 • edited May 15, 2019 by Arkaprava Arkaprava comment Share Follow See all 6 Comments See all 6 6 Comments reply val_pro20 commented May 15, 2019 reply Follow Share could you please explain more 0 votes 0 votes val_pro20 commented May 15, 2019 reply Follow Share Answer is b 0 votes 0 votes Arkaprava commented May 15, 2019 reply Follow Share 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$ 1 votes 1 votes Arkaprava commented May 15, 2019 reply Follow Share Look at my next comment, i hope it'd be clear now. Let me modify the answer as well. 0 votes 0 votes val_pro20 commented May 15, 2019 reply Follow Share to check whether assigning a true value to each ---why you are considering by own.In question it is not mention right ? 0 votes 0 votes Arkaprava commented May 15, 2019 reply Follow Share Yes that was my mistake. I've edited now. 0 votes 0 votes Please log in or register to add a comment.
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. Arkaprava answered May 25, 2019 Arkaprava comment Share Follow See all 0 reply Please log in or register to add a comment.
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. shivam001 answered Dec 18, 2019 shivam001 comment Share Follow See all 0 reply Please log in or register to add a comment.