The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
29 views
What is the time complexity for checking whether an assignment of truth values
to variables x1 … xn satisfies a given formula f(x1,…,xn)?

(A) O(2^n)
(B) O(g(n)) where g is a polynomial
(c) O(log(n))
(D) None of the above
asked in Digital Logic by Active (1.1k points) | 29 views

1 Answer

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.
answered by Active (1.2k points)
edited by
0
could you please explain more
0
Answer is b
0
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.

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,434 questions
53,630 answers
186,007 comments
70,899 users