Answer each question TRUE or FALSE. Will be much appreciate if explain is provid

Question

Answer each question TRUE or FALSE.

Will be much appreciate if explain is provided for each question of why it is True/False...

Thank you.

(a) We know a polynomial time algorithm to solve the Integer Knapsack Problem mark) (1 mark) (1 mark) (1 mark) (1 mark) (1 mark) (g) The Change-Making Problem can be solved optimally by the usual greedy algorithm in all (1 mark) (h) The Fast Fourier Transform can multiply two n-bit numbers in time in O(n 1 mark) (i) The Gale-Shapley algorithm gives the best possible solution to the Stable Marriage Problem (1 mark) G) The Knapsack Problem can be solved in polynomial time by a greedy algorithm if we relax (1 mark) (b) (The decision version of) integer factoring is an NP-complete problem (c) The problem of testing whether an integer is prime is in P. (d) It is not known whether P- BPF. (e) Graph isomorphism testing is in NPn coN P, but not known to be in P (f) 3-SAT is an NP-complete problem. cases for the choosers, but the worst for the proposers. the requirement that the ite ms cannot be divided

Explanation / Answer

True

False

True

False

True

True

False

True

True

True

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.