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: