WBJECA 2025 — Computer PYQ
WBJECA | Computer | 2025The order of an algorithm that finds whether a given Boolean function of n variables produces 1 is
Choose the correct answer:
- A.
constant
- B.
linear
- C.
logarithmic
- D.
exponential
(Correct Answer)
exponential
Explanation
The problem described is known as the Boolean Satisfiability Problem (SAT). It asks whether there exists an assignment of truth values (True or False) to n variables such that a given Boolean formula evaluates to 1 (True).
Complexity Analysis: A Boolean function of n variables can be represented by a truth table. To determine if the function produces 1, in the worst-case scenario, we must evaluate the function for all possible combinations of variable assignments.
Combinations: Since each of the n variables can be either 0 or 1, there are a total of 2n possible input combinations.
The total number of evaluations required is:
Total Evaluations=2n
This growth rate, as a function of the number of variables n, is classified as exponential time complexity, denoted in Big O notation as:
O(2n)
Because the search space grows exponentially with each additional variable, no known algorithm can solve this problem in polynomial time for all cases, making (D) the correct answer.
Explanation
The problem described is known as the Boolean Satisfiability Problem (SAT). It asks whether there exists an assignment of truth values (True or False) to n variables such that a given Boolean formula evaluates to 1 (True).
Complexity Analysis: A Boolean function of n variables can be represented by a truth table. To determine if the function produces 1, in the worst-case scenario, we must evaluate the function for all possible combinations of variable assignments.
Combinations: Since each of the n variables can be either 0 or 1, there are a total of 2n possible input combinations.
The total number of evaluations required is:
Total Evaluations=2n
This growth rate, as a function of the number of variables n, is classified as exponential time complexity, denoted in Big O notation as:
O(2n)
Because the search space grows exponentially with each additional variable, no known algorithm can solve this problem in polynomial time for all cases, making (D) the correct answer.