![GATE 2014 [Set-3]](https://solutionsadda.in/wp-content/uploads/2019/05/green-new-logo.png){kind=logo}
JT(IT) 2018 PART-A General Aptitude
April 4, 2025GATE 2014 [Set-3]
April 4, 2025GATE 2014 [Set-3]
|
Question 48
|
Consider the decision problem 2CNFSAT defined as follows:
- {Φ|Φ is a satisfiable propositional formula in CNF with atmost two literals per clause}
For example, 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.
|
Question 48 Explanation:
Note: Out of Syllabus.
Correct Answer: B
Question 48 Explanation:
Note: Out of Syllabus.