2. Let C be a 3-CNF formula. A≠-assignment to C is a truth assignment that satisfies C, but in such a way that every clause of C has at least one literal set to true, but also has one literal set to false. Prove that, if a is a≠-assignment for a set of clauses, then so it is its inversion a ̅, where the inversion of an assignment is the assignment that is obtained by inverting each assignment value of a (i.e. 1 to 0, and 0 to 1).
This material may consist of step-by-step explanations on how to solve a problem or examples of proper writing, including the use of citations, references, bibliographies, and formatting. This material is made available for the sole purpose of studying and learning - misuse is strictly forbidden.We assume that as input we have the graph G encoded as an adjacency list in a binary notation.
1) We also assume its vertices are counted from 1 to n.
The non-deterministic algorithm will must first call a method to determine a sequence of n+1 numbers from 1 to n.
Then we put the algorithm to verify that each number from the range [1..n] appears only once in the sequence. This can be done simpler by sorting the sequence. The only constraint involves the first and last numbers, which must be the same....