Q38

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