Teaching UGC NET Mock Test Series 2025 (Paper 1 & 2) Theory of Computation Recursively Enumerable Sets, Turing Machines and Undecidability Undecidability
Which of the following problems is NOT NP-complete?
I. Checking satisfiability of arbitrary Boolean formulae
II. Checking satisfiability of Boolean formulae in conjunctive normal form (CNF/product of sums)
III. Checking satisfiability of Boolean formulae in disjunctive normal form (DNF/sum of products)
1
II only
2
III only
3
I only
4
None of the above