Circuit satisfiability problem: given a Boolean combinational circuit composed of AND, OR and NOT gates, is it satisfiable? A one-output Boolean combinational circuit is satisfiable if for some input the output is 1.
1. The circuit satisfiability problem belongs to class NP.
2. The circuit satisfiability problem is at least as hard as any language in NP.
3. Circuit satisfiability is NP-complete.
4. The size of the circuit is Θ(k2 + 1).
5. If P ≠ NP, this situation would contradict the NP-completeness of the problem.
Choose the correct answer from the options given below:
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 is verifiable), NP-hard, hence NP-complete. Statement 4 is not a general fact and statement 5 is false.More Data Structures and Algorithms questions
- Given the expression (A + B * D) / (E − F) + G: 1. The prefix notation is + / + A * D B − E F G 2. The prefix expression is the reverse of…
- Match List I with List II. Choose the correct answer from the options given below:List I List II a. Dijkstra's algorithm I. Calculates path…
- For the weighted graph below, which of the following orders of adding edges can NOT be produced by a minimum spanning tree algorithm? Edges…
- Statement I: Given a graph G = (V, E) in which each vertex v ∈ V has an associated positive weight w(v), we can use linear programming to f…
- Assume that f(n), g(n) and h(n) are asymptotically positive. Which of the following is correct?
- The solution of the recurrence relation T(n) = 3T(n/4) + n log n is