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)$?
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
Answer : B
its 2-SAT problem
2-SAT is a special case of Boolean Satisfiability Problem and can be solved in polynomial time.
64.3k questions
77.9k answers
244k comments
80.0k users