1
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • $\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$ Commented May 6, 2019 at 11:23
  • $\begingroup$ is it like transforming n clauses into 3n nodes in the graph? or did i not get it correctly $\endgroup$ Commented May 6, 2019 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$ Commented May 6, 2019 at 13:18

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\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$ Commented May 6, 2019 at 15:24

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.