i am struggling for quite a while with this. trying to understand why the following function can be calculated in polynomial time(in regards to the input length)

defining a function from assignments of truth values to a set of booleans to 3CNF propositions:

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 understand how can it be computed in a polynomial time in regards to the input size. tried to look everywhere, this site, online, sipser's book and nothing. similar problems are usually from the NP family.

could someone please explain to me how this one can be polynomially computed? i just can't understand that

EDIT: this is how the final 3CNF should look in my opinion: $(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)$ (from $(l_1 \lor l_2\lor...\lor l_n)$).

but what i don't understand is why is it polynomial, could someone please explain to me why can it be computed polynomially in regards to input size?

  • $\begingroup$ You need to build in polynomial time a 3-CNF that is satisfied only by a given assignment. That's easier than deciding satisfiability. For $n=3$ and $x_1=x_2=1$ and $x_3=0$ the solution would be simply a single clause $x_1\land x_2\land\neg x_3$. Try to generalize to 4 variables. $\endgroup$ May 6 '19 at 11:23
  • $\begingroup$ is it like transforming n clauses into 3n nodes in the graph? or did i not get it correctly $\endgroup$
    – hps13
    May 6 '19 at 13:08
  • $\begingroup$ if i understood what you're trying to say correctly, if i have a clause that has more than 3 literals, i.e $(l_1 \lor l_2\lor...\lor l_n)$ then i can transform it 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 don't understand how to utilize it to show it can be computed in polynomial time in regards to the input size $\endgroup$
    – hps13
    May 6 '19 at 13:18

Let's start with solving the problem for 1-CNFs. The proof will be by example. If the truth assignment is $x_1=x_2=1,x_3=0$ then a 1-CNF for which this is the only satisfying assignment is $$ x_1 \land x_2 \land \overline{x_3}. $$ Now let's solve the problem for 2-CNFs, again by example. Continuing with our previous example, here is one possible construction: $$ (x_1 \lor x_2) \land (x_1 \lor \overline{x_2}) \land (x_2 \lor x_3) \land (x_2 \lor \overline{x_3}) \land (\overline{x_3} \lor x_1) \land (\overline{x_3} \lor \overline{x_1}). $$ More generally, we replace $x_i$ with $(x_i \lor x_j) \land (x_i \lor \overline{x_j})$ for an arbitrary $j \neq i$.

Your problem can be solved in a very similar way.

  • $\begingroup$ could you check the comments in the main post please @Yuval Filmus? this is what i tried to do but with three variables. however, i did not understand how to prove using this that the function can be computed in a polynomial time(with respect to the input size) $\endgroup$
    – hps13
    May 6 '19 at 15:24

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.