+1 vote
134 views

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)$?

1. $O(2^n)$
2. $O(g(n))$ where $g$ is a polynomial
3. $O(log(n))$
4. None of the above

edited | 134 views
0
is it option D ?
0

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

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.
by Active (2.1k points)
edited
0
0
+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$
0
Look at my next comment, i hope it'd be clear now. Let me modify the answer as well.
0
to check whether assigning a true value to each ---why you are considering by own.In question  it is not mention right ?
0
Yes that was my mistake. I've edited now.
$O(2^{n})$ is for assigning truth values.

Since there are $n$ variables $x_{1},x_{2},.....x_{n}$ and each can take $1$ of the $2$ values true or false.

so $2*2*2.....n$ times = $2^{n}$ ways are there to assign truth values to the given formula.

Question is asking whether the combination which we assign out of the $2^{n}$ possible cases satisfies the given formula or not.

so each of the $2^{n}$ cases may satisfy or not satisfy the given formula.

So we have $2^{2^{n}}$ possibility = $O(2^{2^{n}})$
by Boss (17.2k points)
edited by
0
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.
by Active (2.1k points)

1
+1 vote
2
3
4
5
+1 vote
6