In the following discussion, we fix a simplified instance \((F, k)\)  for the MaxSAT problem
on variables \(\lbrace x_1, x_2, \ldots , x_n\rbrace \) , where \(F = C_1 \wedge C_2 \wedge \ldots \wedge C_m\) .
We first observe the following result, which can be derived based on a general framework
proposed by Yannakakis [1]}:
