.Yes it is B

The Gateway to Computer Science Excellence

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

+2

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

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.

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

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$

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,741 questions

57,251 answers

198,056 comments

104,680 users