Question

Let CL and Sat denote two different decision problems. Sat denotes Boolean Satisfiability, which is known to be NP-hard. The goal is to show that CL is NP-hard as well. Recall that the notation XX ≤P YY is read as "XX is reducible to YY in polynomial time"). To show that CL is also NP-hard, it is required to exhibit a deterministic polynomial-time transformation R that does which of the following choices?

(a) R transforms every instance of CL into some instance of Sat, and ensures that the Sat instance is "yes" whenever the CL instance is yes.

(b) R transforms every instance of Sat into some instance of CL, and ensures that the CL instance is "yes" whenever the Sat instance is yes.

(c) R transforms every instance of CL into some instance of Sat, and ensures that the Sat instance is "yes" if and only if the CL instance is yes.

(d) R transforms every instance of Sat into some instance of CL, and ensures that the CL instance is "yes" if and only if the Sat instance is yes.

Answer 1

To show that the decision problem CL is NP-hard, a deterministic polynomial-time transformation R must be created that transforms every instance of Sat into an instance of CL such that the CL is 'yes' if and only if the Sat instance is 'yes'. This establishes that CL is at least as hard as the known NP-hard problem Sat.

Step-by-step explanation:

To demonstrate that the decision problem CL is NP-hard, given that the Boolean Satisfiability problem (Sat) is known to be NP-hard, we need to find a deterministic polynomial-time reduction from Sat to CL. This involves creating a transformation R that meets specific conditions.

The correct choice among the provided options is:

• (d) R transforms every instance of Sat into some instance of CL, and ensures that the CL instance is "yes" if and only if the Sat instance is yes.

This means that for every instance of Sat, there is a corresponding instance of CL such that Sat is satisfiable if and only if CL has a solution. If we can show this transformation R exists and it can be computed in polynomial time, then we have proven that CL is NP-hard. This is because we have shown that a known NP-hard problem (Sat) can be reduced to CL in polynomial time. If Sat can be solved using CL, and Sat is known to be hard for NP, then CL must be at least as hard as Sat, which makes CL also NP-hard.