Bissoy.com
Doctors Medicines MCQs Q&A

Which of the following problems is NOT NP-complete? I. Checking satisfiability of arbitrary Boolean formulae II. Checking satisfiability of Boolean formulae in conjunctive normal form (CNF/product of sums) III. Checking satisfiability of Boolean formulae in disjunctive normal form (DNF/sum of products)

Which of the following problems is NOT NP-complete? I. Checking satisfiability of arbitrary Boolean formulae II. Checking satisfiability of Boolean formulae in conjunctive normal form (CNF/product of sums) III. Checking satisfiability of Boolean formulae in disjunctive normal form (DNF/sum of products) Correct Answer None of the above

The correct answer is option 3.

Concept:

NP Problem:

The NP problems set of problems whose solutions are hard to find but easy to verify and are solved by Non-Deterministic Machines in polynomial time.

NP-Hard Problem:

A Problem X is NP-Hard if there is an NP-Complete problem Y, such that Y is reducible to X in polynomial time. NP-Hard problems are as hard as NP-Complete problems. NP-Hard Problem need not be in NP class.

NP-Complete Problem:

A problem X is NP-Complete if there is an NP problem Y, such that Y is reducible to X in polynomial time. NP-Complete problems are as hard as NP problems. A problem is NP-Complete if it is a part of both NP and NP-Hard Problem. A non-deterministic  Turing machine can solve the NP-Complete problems in polynomial time.

Relation between Np problems:

[ src="//storage.googleapis.com/tb-img/production/22/02/F1_Shraddha_Harshita_21.2.2022_D3.png" style="width: 328px; height: 200px;">

Option 1: Checking satisfiability of arbitrary Boolean formulae.

False, Cook–Levin theorem, also known as Cook's theorem, states that the Boolean satisfiability problem is NP-complete. That is, it is in NP, and any problem in NP can be reduced in polynomial time by a deterministic Turing machine to the Boolean satisfiability problem.

Option 2: Checking satisfiability of Boolean formulae in conjunctive normal form (CNF/product of sums)

False, The k-SAT problem is the problem of finding a satisfying assignment to a boolean formula expressed in CNF in which each disjunction contains at most k variables. 3-SAT is NP-complete (like any other k-SAT problem with k>2) while 2-SAT is known to have solutions in polynomial time. As a consequence, the task of converting a formula into a DNF, preserving satisfiability, is NP-hard. Dually, converting into CNF, preserving validity, is also NP-hard. hence equivalence-preserving conversion into DNF or CNF is again NP-hard.

Option 3: Checking satisfiability of Boolean formulae in disjunctive normal form (DNF/sum of products)

False, The Boolean satisfiability problem on conjunctive normal form formulas is NP-hard; by the duality principle, so is the falsifiability problem on DNF formulas. Therefore, it is co-NP-hard to decide if a DNF formula is a tautology.

Related Questions

Which of the following problems are decidable? I. Checking whether two regular languages are equivalent languages II. Checking whether two non-deterministic finite automata accept the same language III. Checking whether two context free grammars generate equivalent languages  IV. Checking whether a language of a context free grammar is non-empty
Let G1 and G2 be arbitrary context free languages and R an arbitrary regular language. Consider the following problems: (A) Is L(G1) = L(G2)? (B) Is L(G2) ≤ L(G1)? (C) Is L(G1) = R? Which of the problems are undecidable ? Choose the correct answer from the options given below:
Imagine, you are solving a classification problems with highly imbalanced class. The majority class is observed 99% of times in the training data. Your model has 99% accuracy after taking the predictions on test data. Which of the following is true in such a case?
1. Accuracy metric is not a good idea for imbalanced class problems.
2.Accuracy metric is a good idea for imbalanced class problems.
3.Precision and recall metrics are good for imbalanced class problems.
4.Precision and recall metrics aren't good for imbalanced class problems.
Which of the following are products and services bought by final consumers for personal consumption? These include convenience products, shopping products, specialty products, and unsought products.
In the following figure, square represents the people who use the product of Colorbar, the triangle represents the people who use products of NYX, the circle represents people who use products of M.A.C., the rectangle represents people who use products of Maybelline and semi-circle represents the people who use the products of Lakme. Which set of letter(s) represents people who use products of M.A.C. and NYX only?
In the following figure, square represents the people who use the product of Colorbar, the triangle represents the people who use products of NYX, the circle represents people who use products of M.A.C., the rectangle represents people who use products of Maybelline and semi-circle represents the people who use the products of Lakme. Which set of letters represents people who use only products of Colorbar? 
interface Base{ boolean m1 (); byte m2(short s);}

which two code fragments will compile?
1. interface Base2 implements Base {}2. abstract class Class2 extends Base { public boolean m1(){ return true; }}3. abstract class Class2 implements Base {}4. abstract class Class2 implements Base { public boolean m1(){ return (7 > 4); }}5. abstract class Class2 implements Base { protected boolean m1(){ return (5 > 7) }}
A function (A, B, C) defined by three boolean variables A, B, and C when expressed as the sum of products is given by: F = A̅.B̅.C̅ + A̅.B.C̅ + A.B̅.C̅ where, A̅, B̅, and C̅ are the complements of the respective variables. The product of sums (POS) form of the function F is
What kind of clauses are available in conjunctive normal form ?
What kind of clauses are available in Conjunctive Normal Form?