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 ?
- Both $\text{3-CF-SAT}$ and $\text{3-DF-SAT}$ are in NP but only $\text{3-CF-SAT}$ is NP-complete
- Both $\text{3-CF-SAT}$ and $\text{3-DF-SAT}$ are in NP-complete
- Both $\text{3-CF-SAT}$ and $\text{3-DF-SAT}$ are in P
- Both $\text{3-CF-SAT}$ and $\text{3-DF-SAT}$ are in NP but only $\text{3-DF-SAT}$ is NP-complete
- Neither $\text{3-CF-SAT}$ nor $\text{3-DF-SAT}$ are in P