very interested in knowing if this conversion is possible, i.e if we can create a function that can be computed in a polynomial time is respect to the input size, so that for an input of boolean assignments into a set of variables the function generates output of a 3cnf proposition as following:
the function gets an assignment of truth values to a set of n boolean variables $x_1,x_2,...,x_n$ (n ≥ 3) (meaning each boolean variables gets either 0 or 1).
the function returns a 3CNF proposition that upholds(maintains) the following:
1)each clause of the proposition contains exactly three literals
2)the proposition consists of only the variables $x_1,x_2,..,x_n$
3)the three literals in each clause are of different variables(there are no double literals in the clause, and none of the clauses consists of complimentary literals)
4)the proposition is satisfiable and the only assignment that satisfies the proposition is the assignment the function obtained as an input.
prove that the given function can be calculated in a polynomial time in regards to the input size
i don't get how it can be polynomially computed in respect to input size. tried to look everywhere but couldn't find a solution for that.
what i think is that we need to arrange the input into an "appropriate" 3cnf form, as following: $(l_1∨l_2∨...∨l_n)$ into $(l_1 \lor l_2 \lor x_1) \land (\lnot x_1 \lor l_3 \lor x_2) \land (\lnot x_2 \lor l4 \lor x_3)\land ... \land(\lnot x_{n-3} \lor l_{n-1} \lor l_n)$
but i really not sure if it is right or how can it be used in order to show it can be computed in polynomial time.
please help if you can, totally lost here.
