The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+6 votes

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.
asked in Theory of Computation by Veteran (101k points)
retagged by | 902 views

3 Answers

+7 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.

answered by Boss (42.8k points)
selected by
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.
answered by Active (3.6k points)
+1 vote

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 details.

answered by Loyal (8.4k points)

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

39,440 questions
46,623 answers
57,022 users