Consider the (5,k)-SAT problem: Input: A boolean formula in…
Consider the (5,k)-SAT problem: Input: A boolean formula in CNF form such that there are at most five literals in each clause, and an integer k ≥ 1.Output: An assignment of variables such that exactly k clauses are unsatisfied, or return NO if such an assignment does not exist. Prove that (5,k)-SAT is NP-complete.