Circuit satisfiability problem: given a Boolean combinational circuit of AND, OR and NOT gates, is it satisfiable (is there an input for which the output is 1)? 1. Circuit-SAT belongs to NP. 2. Circuit-SAT is at least as hard as any language in NP. 3. Circuit-SAT is NP-complete. 4. The size of the circuit is Θ(k² + 1). 5. If P ≠ NP, this would contradict the NP-completeness of the problem.

1. A1, 3, 4 Only
2. B2, 4, 5 Only
3. C1, 2, 3 Only
4. D2, 3, 4 Only

Pick an option to check yourself, or open the answer below.

Show answer & explanation

Correct answer: C. 1, 2, 3 Only

Explanation

Circuit-SAT is in NP (a satisfying input can be checked quickly), every NP language reduces to it (NP-hard), so it is NP-complete (CLRS Lemma 34.5–34.6). Statements 4 and 5 are not part of this result.