NP-Complete

Question 1

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

A
NP-Complete.
B
solvable in polynomial time by reduction to directed graph reachability.
C
solvable in constant time since any input instance is satisfiable.
D
NP-hard, but not NP-complete.
Theory-of-ComputationNP-CompleteGATE 2014 [Set-3]Video-Explanation
Question 1 Explanation: 
Note: Out of Syllabus.
There is 1 question to complete.

Access quiz wise question and answers by becoming as a solutions adda PRO SUBSCRIBER with Ad-Free content

If you have registered and made your payment please contact solutionsadda.in@gmail.com to get access