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
- NP-complete
- solvable in polynomial time by reduction to directed graph reachability.
- solvable in constant time since any input instance is satisfiable.
- NP-hard but not NP-complete.