Consider the statements:
I. There does not exist a polynomial-time algorithm to solve integer linear programming problems.
II. The main focus of PERT is 'minimising time'.
Choose the correct option about statements I and II.
Pick an option to check yourself, or open the answer below.
Show answer & explanation
Correct answer: A. I is true; II is true
Explanation
ILP is NP-hard, so no polynomial algorithm is known (none exists unless P = NP). PERT is a time-oriented technique.More Discrete Structures and Optimization questions
- Four persons P, Q, R and S are in custody and one of them has committed a crime. They say: P: Q did it. Q: S did it. R: I did not do it. S:…
- There are three boxes. The first box has 2 white, 3 black and 4 red balls. The second box has 3 white, 2 black and 2 red balls. The third b…
- Consider the primal problem: Maximize z = 5x1 + 12x2 + 4x3 subject to x1 + 2x2 + x3 = 10 2x1 − x2 + 3x3 = 8 x1, x2, x3 ≥ 0 Its dual problem…
- The logic expression (P′ ∧ Q) ∨ (P ∧ Q′) ∨ (P ∧ Q) is equivalent to
- Consider α, β, γ as logical variables. Which of the following are correct logical equivalences? (A) α ∧ (β ∨ γ) ≡ (α ∧ β) ∨ (α ∧ γ) (B) α ∨…
- Let ({a, b}, *) be a semigroup where a * a = b. Consider: (A) a * b = b * a (B) b * b = b Choose the most appropriate answer from the optio…