Q1 /5 Consider n binary variables x i (1 ≤ i ≤ n) and m equations f(j) = max(g {j1}(x a), g...
Accenture technical mcq question, verified with a worked answer. Free to practise - no sign-up.
/5
Consider n binary variables x_i (1 ≤ i ≤ n) and m equations f(j) = max(g_{j1}(x_a), g_{j2}(x_b), g_{j3}(x_c)) (1 ≤ j ≤ m; 1 ≤ a_j, b_j, c_j ≤ n) are predefined constant indices. g_{jk}(x) (1 ≤ k ≤ 3) is also a predefined function that is either g_{jk}(x) = x or g_{jk}(x) = 1 - x. Here, we want to determine if there exists a tuple x_i (1 ≤ i ≤ n) such that min_{1≤j≤m} f(j) = 1.
Select the correct statement about an algorithm to solve the problem above with a single processor.
Show answer & explanation
This problem is a variant of 3-SAT (satisfiability) in disguise. Each equation f(j) = max(g_{j1}(x_a), g_{j2}(x_b), g_{j3}(x_c)) represents a disjunctive clause (OR of three literals), and we need all m clauses to be satisfied (min = 1). This is the Boolean satisfiability problem, which is NP-complete. Option A is false because no known polynomial-time algorithm exists for NP-complete problems. Option C is false because algorithms do exist (though exponential). Option D is incorrect because B is correct.
Step-by-step Derivation:
Problem formulation: We need min_j f(j) = 1, meaning all f(j) must equal 1. Each f(j) = max(g_{j1}(x_a), g_{j2}(x_b), g_{j3}(x_c)) = 1 requires at least one of the three terms to be 1 (logical OR). Since g_{jk}(x) is either x or 1-x (literal or its negation), each clause is a disjunction of three literals. This is exactly the 3-SAT problem: given m clauses with 3 literals each over n boolean variables, determine if a satisfying assignment exists. 3-SAT is proven NP-complete (Cook's theorem, 1971). No polynomial-time algorithm is known for any NP-complete problem; such an algorithm would prove P=NP. The best known algorithms have exponential time complexity (2^n or similar). Therefore, statement B accurately reflects the computational complexity status of this problem.