search
Log In
9 votes
2k views

Consider the decision problem $2CNFSAT$ defined as follows:

$$\left\{ \phi \mid \phi \text{ is a satisfiable propositional formula in CNF with at most two literals per clause}\right\}$$

For example, $\phi = (x1 \vee x2) \wedge (x1 \vee \bar{x3}) \wedge (x2 \vee x4)$ is a Boolean formula and it is in $2CNFSAT$.

The decision problem $2CNFSAT$ is

  1. NP-complete
  2. solvable in polynomial time by reduction to directed graph reachability.
  3. solvable in constant time since any input instance is satisfiable.
  4. NP-hard but not NP-complete.
in Theory of Computation
retagged by
2k views

3 Answers

9 votes
 
Best answer

2CNF is P.

SO A) & D) are ruled out.

C) solvable in constant time since any input instance is satisfiable. => This is false. Input instanece where this is false x1=F, x2=F

Then it becomes false.

Answer B)  is true.


selected by
1
C) is not false because of your given reason. Satisfiability means that you can have an assignment of values which make the expression true which you can clearly do for the given expression. It's false since you could have an expression like (A AND ~A) which always evaluates to false and is thus not satisfiable.
3 votes
this problem is directly reduced to strongly connected component and hence B.
3 votes

2CNF-SAT can be reduced to strongly connected components problem. And strongly connected component has a polynomial time solution. Therefore 2CNF-SAT is polynomial time solvable. See https://en.wikipedia.org/wiki/2-satisfiability#Strongly_connected_componentsfor details.

Answer:

Related questions

12 votes
5 answers
1
3.6k views
Suppose a polynomial time algorithm is discovered that correctly computes the largest clique in a given graph. In this scenario, which one of the following represents the correct Venn diagram of the complexity classes P, NP and NP Complete (NPC)?
asked Sep 28, 2014 in Theory of Computation jothee 3.6k views
14 votes
2 answers
2
3k views
Consider two decision problems $Q_1, Q_2$ such that $Q_1$ reduces in polynomial time to 3-SAT and 3-SAT reduces in polynomial time to $Q_2$. Then which one of the following is consistent with the above statement? $Q_1$ is in NP, $Q_2$ is NP hard. $Q_2$ is in NP, $Q_1$ is NP hard. Both $Q_1$ and $Q_2$ are in NP. Both $Q_1$ and $Q_2$ are in NP hard.
asked Feb 12, 2015 in Theory of Computation jothee 3k views
5 votes
1 answer
3
2.1k views
A problem in NP is NP-complete if it can be reduced to the 3-SAT problem in polynomial time the 3-SAT problem can be reduced to it in polynomial time it can be reduced to any other problem in NP in polynomial time some problem in NP can be reduced to it in polynomial time
asked Oct 31, 2014 in Algorithms Ishrat Jahan 2.1k views
15 votes
2 answers
4
3.7k views
Let $\delta$ denote the minimum degree of a vertex in a graph. For all planar graphs on $n$ vertices with $\delta \geq 3$, which one of the following is TRUE? In any planar embedding, the number of faces is at least $\frac{n}{2}+2$ In any planar embedding, the number of faces ... is less than $\frac{n}{2}+2$ There is a planar embedding in which the number of faces is at most $\frac {n}{\delta+1}$
asked Sep 28, 2014 in Graph Theory jothee 3.7k views
...