Advanced Algorithms · Quiz 2 · Sep 2023

This solution is definitely not optimal

This solution may or may not be optimal, depends on the values of the payouts.

1/2

1/4

1

2

Yes, because there is a reduction from EXACT-COVER-BY-3-SETS to EXACT- COVER-BY-4-SETS.

Yes, because there is a reduction from EXACT-COVER-BY-4-SETS to EXACT- COVER-BY-3-SETS.

EXACT-COVER-BY-4-SETS may or may not be NP-Complete.

If X can be solved in polynomial time, then so can Y.

X can be solved in polynomial time if and only if Y can be solved in polynomial time.

If X cannot be solved in polynomial time, then neither can Y.

If Y cannot be solved in polynomial time, then neither can X.       **Mathematical Thinking** **Section Id :** 64065348603 **Section Number :** 10 **Section type :** Online **Mandatory or Optional :** Mandatory **Number of Questions :** 3 **Number of Questions to be attempted :** 3 **Section Marks :** 30 **Display Number Panel :** Yes **Group All Questions :** No **Enable Mark as Answered Mark for Review and** Yes **Clear Response :** **Maximum Instruction Time :** 0