recategorized by
1,018 views
3 votes
3 votes

A formula is said to be a $3$-CF-formula if it is a conjunction (i.e., an AND) of clauses, and each clause has at most $3$ literals. Analogously, a formula is said to be a $3$-DF-formula if it is a disjunction (i.e., an OR) of clauses of at most $3$ literals each.

Define the languages $3$-CF-SAT and $3$-DF-SAT as follows:

$$3 \text{-CF-SAT}=\{ \Phi \mid \Phi \text{ is a } \textit{ satisfiable } 3\text{-CF formula} \}$$

$$3\text{-DF-SAT}=\{ \Phi \mid  \Phi \text{ is a } \textit{satisfiable } 3\text{-DF formula} \}$$

Which of the following best represents our current knowledge of these languages ?

  1. Both $\text{3-CF-SAT}$ and $\text{3-DF-SAT}$ are in NP but only $\text{3-CF-SAT}$ is NP-complete
  2. Both $\text{3-CF-SAT}$ and $\text{3-DF-SAT}$ are in NP-complete
  3. Both $\text{3-CF-SAT}$ and $\text{3-DF-SAT}$ are in P
  4. Both $\text{3-CF-SAT}$ and $\text{3-DF-SAT}$ are in NP but only $\text{3-DF-SAT}$ is NP-complete
  5. Neither $\text{3-CF-SAT}$ nor $\text{3-DF-SAT}$ are in P
recategorized by

1 Answer

6 votes
6 votes

3 SAT where all the clauses are in conjunctive normal form is the well known NP-complete problem.

3 SAT with clauses in Disjunctive normal form lies in P class. Now one doubt you might get while solving this question is, if 3 SAT with CNF is NP-complete and 3 SAT with DNF belongs to P, then why not to convert CNF formula to equivalent DNF formula?? If we can do this conversion, then we can solve 3 SAT CNF too in polynomial time using the algorithm for checking 3 SAT DNF. 

But please note that this conversion process is not polynomial. When you convert a CNF formula to equivalent DNF formula, it can have much much larger terms than that of original CNF formula, so this conversion process is not polynomial, it is exponential. Hence the idea of converting 3CNF to 3DNF won't work.

Option A is correct.

Nice read: https://math.stackexchange.com/questions/159591/solving-sat-by-converting-to-disjunctive-normal-form

 

 

Answer:

Related questions

12 votes
12 votes
2 answers
3
Arjun asked Dec 18, 2018
1,318 views
What are the last two digits of $1! + 2! + \dots +100!$?$00$$13$$30$$33$$73$
4 votes
4 votes
2 answers
4
Arjun asked Dec 18, 2018
4,149 views
Which of the following decimal numbers can be exactly represented in binary notation with a finite number of bits ?$0.1$$0.2$$0.4$$0.5$All the above