retagged by
3,752 views
11 votes
11 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.
retagged by

3 Answers

Best answer
9 votes
9 votes

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
Answer:

Related questions

13 votes
13 votes
5 answers
1
6 votes
6 votes
1 answer
3
54 votes
54 votes
5 answers
4
go_editor asked Sep 28, 2014
13,545 views
The length of the shortest string NOT in the language (over $\Sigma = \{a, b\})$ of the following regular expression is _______.$$a^*b^*(ba)^*a^*$$