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.


If I understand correctly, the question is as follows:

Given a boolean assignment to variables $x_1,\dots,x_n$, is there a polynomial algorithm to construct a formula $\varphi(x_1,\dots,x_n)$ in 3-CNF (such that each clause contains exactly three different variables) such that $\varphi$ is satisfied exactly by the given assignment and no other?

The answer is yes, you can quite easily construct such formula in linear time. We can assume that the given assignment is $(1,1,\dots,1)$. If there are zeros, we can take the same formula, where we just negate all the literals which are assigned $0$. You split your variables in triplets (if $n$ is not divisible by three, you can reuse some of the previous variables for the last triplet), and for each triplet $x,y,z$ you add the following seven clauses to your formula:

$(x\lor y \lor z) \land (x\lor y \lor \bar z) \land(x\lor \bar y \lor z) \land(x\lor \bar y \lor \bar z) \land(\bar x\lor y \lor z) \land(\bar x\lor y \lor \bar z) \land(\bar x\lor \bar y \lor z)$

Each of the clauses prohibits $(x,y,z)$ to take one of the other assignments than $(1,1,1)$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.