recategorized by
514 views
0 votes
0 votes

 Which of the following problems is $\text{NOT NP}$-complete?

  1. Checking satisfiability of arbitrary Boolean formulae
  2. Checking satisfiability of Boolean formulae in conjunctive normal form $\text{(CNF}$/product of sums)
  3. Checking satisfiability of a Boolean formulae in disjunctive normal form $\text{(DNF}$/sum of products)

 

  1. None of the above
  2. $\text{II}$ only
  3. $\text{III}$ only
  4. $\text{I}$ only
recategorized by

1 Answer

0 votes
0 votes
Checking satisfiability of a boolean expression means it asks whether the variables of a given Boolean formula can be consistently replaced by the values TRUE or FALSE in such a way that the formula evaluates to TRUE.

It is the first problem to be proved NP complete.

now ,

so option a is true.

Now a boolean formula can either be in Conjunctive normal form or in Disjunctive normal form and we can convert from Conjunctive normal form to Disjunctive normal form .so both are equivalent when we try to check its satisfiability.

so all of the given problems is NP complete.

Correct option is None of these.
Answer:

Related questions

0 votes
0 votes
1 answer
1
0 votes
0 votes
1 answer
2
admin asked Jan 5, 2019
373 views
How many Boolean functions in one variable are $\text{NOT}$ idempotent: i.e. they do not satisfy $\forall a.f(f(a)) = f(a).$$4$Infinite$1$$0$
1 votes
1 votes
2 answers
3
admin asked Jan 5, 2019
381 views
How many different Boolean circuits of $n$ variables are there?None of the above$n^{2^{n}}$$2^{2^{n}}$$2^{n}$
0 votes
0 votes
3 answers
4
admin asked Jan 5, 2019
835 views
Which Boolean function does the following Karnaugh map represent?Inclusive $\text{NOR}$Exclusive $\text{NOR}$Exclusive $\text{OR}$Inclusive $\text{OR}$