in the half 3-cnf satisfiability problem, we are given a 3-cnf formula with n variables and m clauses, where m is even. we wish to determine whether there exists a truth assignment to the variables of such that exactly half the clauses evaluate to 0 and exactly half the clauses evaluate to 1. prove that the half 3-cnf satisfiability problem is np-complete
