The Gateway to Computer Science Excellence

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

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

+8 votes

Best answer

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

+2 votes

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,737 questions

57,301 answers

198,297 comments

104,999 users