You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
{{ message }}
This repository has been archived by the owner on Mar 3, 2024. It is now read-only.
Consider the straightforward (nonpolynomial-time) reduction in the proof of Theorem 34.9. Describe a circuit of size $n$ that, when converted to a formula by this method, yields a formula whose size is exponential in $n$.
Construct the circuit as follows: one input $x_1$ followed by a NOT gate, then followed AND gates which each connects all the outputs of previous steps.
We can encode the circuit in $O(n^k)$, but the formula yielded grows exponentially in each step.
34.4-2
Show the 3-CNF formula that results when we use the method of Theorem 34.10 on the formula (34.3).
Professor Jagger proposes to show that SAT $\le_\text{P}$ 3-CNF-SAT by using only the truth-table technique in the proof of Theorem 34.10, and not the other steps. That is, the professor proposes to take the boolean formula $\phi$, form a truth table for its variables, derive from the truth table a formula in 3-DNF that is equivalent to $\neg \phi$, and then negate and apply DeMorgan's laws to produce a 3-CNF formula equivalent to $\phi$. Show that this strategy does not yield a polynomial-time reduction.
Suppose the number of variables in the formula is $n$, the number of rows in the truth table is $2^n$.
34.4-4
Show that the problem of determining whether a boolean formula is a tautology is complete for co-NP. (Hint: See Exercise 34.3-7.)
Suppose the language of determining whether a boolean formula is a tautology is $L$ and the boolean formula is denoted by $\phi$. Then $\overline{L}$ is equivalent to 3-CNF-SAT with formula $\neg \phi$, therefore $\overline{L}$ is complete for NP. Based on Exercise 34.3-7, $L$ is complete for co-NP.
34.4-5
Show that the problem of determining the satisfiability of boolean formulas in disjunctive normal form is polynomial-time solvable.
The formula in disjunctive normal form evaluates to 1 if any of the clauses in it could be evaluated to 1. A cluase could be evaluated to 1 if there isn't a literal $x$ that both $x$ and $\neg x$ appeared in the clause. Thus suppose there are $n$ clauses and the maximum number of literals in one clause is $m$, the time complexity is $O(nm^2)$.
34.4-6
Suppose that someone gives you a polynomial-time algorithm to decide formula satisfiability. Describe how to use this algorithm to find satisfying assignments in polynomial time.
Suppose the algorithm is $A$, the formula is $\phi$ and the variables are $(x_1, ..., x_n)$.
If $A$ rejects $\phi$, then there is no solution.
Else if $A$ accepts $\phi$, then for each $x_i$, replace $x_i$ by 0, if the transformed formula $\phi'$ is accepted by $A$, then $x_i = 0$, otherwise $x_i = 1$.
34.4-7
Let 2-CNF-SAT be the set of satisfiable boolean formulas in CNF with exactly 2 literals per clause. Show that 2-CNF-SAT $\in$ P. Make your algorithm as efficient as possible. (Hint: Observe that $x \vee y$ is equivalent to $\neg x \rightarrow y$. Reduce 2-CNF-SAT to an efficiently solvable problem on a directed graph.)