Satisfiability Problem · Theory Problems

Lesson 2

Nikolai Chukhin · Alexander S. Kulikov

Advanced Problems.

  1. (20 points) If \(F\) and \(F'\) are sets of clauses, let \(F \sqcup F'\) stand for any other set obtained from \(F \cup F'\) by replacing one or more clauses \(C\) of \(F\) by \(x \cup C\) and one or more clauses \(C'\) of \(F'\) by \(\bar{x}\cup C'\), where \(x\) is a new variable; then \(F \sqcup F'\) is unsatisfiable whenever \(F\) and \(F'\) are both unsatisfiable. For example, if \(F = \{\varepsilon\}\) and \(F' = \{1, \bar{1}\}\), then \(F \sqcup F'\) is either \(\{2, 1\bar{2}, \bar{1}\bar{2}\}\) or \(\{2, 1, \bar{2}\}\) or \(\{2, 1\bar{2}, \bar{1}\}\).

    A set of clauses is minimally unsatisfiable if it is unsatisfiable, yet becomes satisfiable if any clause is deleted. Show that, if \(F\) and \(F'\) have no variables in common, then \(F \sqcup F'\) is minimally unsatisfiable if and only if \(F\) and \(F'\) are minimally unsatisfiable.

  2. (20 points) Prove that the Boolean function \(f(x_{1}, …, x_{n})\) is expressible as a conjunction of Horn clauses if and only if \[f(x_{1}, …, x_{n}) = f(y_{1}, …, y_{n}) = 1 \quad \text{implies}\quad f(x_{1} \land y_{1}, …, x_{n} \land y_{n}) = 1\] for all Boolean values \(x_{j}\) and \(y_{j}\).
  3. (20 points) To ensure that \(x_{1} + \dotsb + x_{n}\) is at most \(r\), introduce \((n - r) r\) new variables \(s_{j}^{k}\) for \(j \in [n - r], k \in [r]\). If \(F\) is any satisfiable problem and if we add the following \((n - r - 1) r + (n - r) (r + 1)\) clauses: \[\begin{align*}(\bar{s}_{j}^{k}&\lor s^{k}_{j + 1}),&&\text{for }j \in [n - r - 1], k \in [r], \\ (\bar{x}_{j + k}\lor&\bar{s}_{j}^{k}\lor s_{j}^{k+1}),&&\text{for }j \in [n - r], k \in \{ 0, 1, \dotsc, r \},\end{align*}\] where \(\bar{s}_{j}^{k}\) is omitted when \(k = 0\) and \(s_{j}^{k + 1}\) is omitted when \(k = r\).

    1. (15 points) Prove that then the new set of clauses is satisfiable if and only if \(F\) is satisfiable with \(x_{1} + \dotsb + x_{n} \le r\).
    2. (5 points) Suppose we wish to impose a sequence of constraints \(x_{1} + \dotsb + x_{i} \le r_{i}\) for \(i \in [n]\). How can this be done nicely?
    Hint:
    Show that \(s_{j}^{k}= 1\) whenever \(x_{1} + \dotsb + x_{j + k - 1}\ge k\).
  4. (20 points) Given an undirected graph \(G\) with \(n\) vertices, construct a randomized algorithm that determines whether \(G\) can be properly colored using \(3\) colors in time \(n^{O(1)}\cdot 1.5^{n}\).
    Hint:
    What if we forbid one color for each vertex? Then we would obtain two variants for each vertex. Consider how the \(\mathrm{SAT}\) problem can assist in solving this instance.
  5. (20 points) Construct a \((\frac{4}{3})^{n}\) randomized algorithm for the \(3\)-\(\mathrm{SAT}\) problem.
  6. (25 points) Consider the Subadditivity problem: given two sequences \(A,B\) indexed by \([n]\) and a sequence \(C\) indexed by \(\{2,\dotsc,2n\}\), decide whether there exist indices \(i,j\in[n]\) such that \(A[i] + B[j] > C[i+j]\).

    The Min-plus convolution problem is defined as follows: given two sequences of size \(n\), of real numbers \(A\) and \(B\), output a sequence \(C\) such that, for every \(k \in \{ 2, \dotsc, 2n \}\), \[C[k] = \min_{i,j \in [n] \colon i+j = k}\bigl( A[i] + B[j] \bigr).\]

    Show that, if there exists an algorithm for Subadditivity that works in time \(O(n^{2 - \varepsilon})\) for some \(\varepsilon > 0\), then there exists a constant \(\delta > 0\) and an algorithm for Min-plus convolution that works in time \(O(n^{2 - \delta})\).

  7. (25 points) Consider the LCS problem: given two strings \(a, b\) of size \(n\), one asks what is the length of their longest common substring. Prove that if LCS can be solved in time \(O(n^{2 - \varepsilon})\), for some \(\varepsilon > 0\), then one can solve the satisfiability problem in time \(O((2 - \delta(\varepsilon))^{n}\cdot n^{O(1)})\) time.
    Hint:
    At first, apply a reduction from SAT to Orthogonal Vectors problem. Then, show how an algorithm for LCS can help in solving Orthogonal Vectors problem.
  8. (25 points) In the \(\mathrm{MAX}\)-\(2\)-\(\mathrm{SAT}\) problem, one is given a formula \(F\) in \(2\)-\(\mathrm{CNF}\) and an integer \(t\). The question is whether it is possible to satisfy at least \(t\) clauses.

    Assume that two matrices \(A, B \in \mathbb{F}^{n \times n}\) can be multiplied in time \(O(n^{\omega})\) for some \(\omega \ge 2\). Then, show that the \(\mathrm{MAX}\)-\(2\)-\(\mathrm{SAT}\) problem can be solved in time \(n^{O(1)}\cdot 2^{n \cdot \frac{\omega}{3}}\).

  9. (30 points) It might seem that 3SAT problems on \(n\) variables are always easy when there are very few clauses, say \(2n\) clauses. We shall prove, however, that any set of \(m\) ternary clauses on \(n\) variables can be transformed mechanically into another set of ternary clauses on \(N = O(m)\) variables in which no variable occurs more than four times. The transformed problem is satisfiable if and only if the original problem was; thus it is not any simpler, although (with at most \(4N\) literals) it has at most \(\tfrac{4}{3}N\) clauses.

    • (a) (5 points) First replace the original \(m\) clauses by \(m\) new clauses \((X_{1} \vee X_{2} \vee X_{3}), …, (X_{3m-2}\vee X_{3m-1}\vee X_{3m})\), on \(3m\) new variables, and show how to add \(3m\) clauses of size 2 so that the resulting \(4m\) clauses have exactly as many solutions as the original.

    • (b) (10 points) Construct 16 unsatisfiable ternary clauses on 15 variables, where each variable occurs at most four times.

    • (c) (5 points) Remove one of the clauses from solution (b) and find all solutions of the 15 clauses that remain.

    • (d) (10 points) Use (a), (b), and (c) to prove the \(N\)-variable result claimed above.

    Hint:
    (b): If \(F\) and \(F'\) are sets of clauses, let \(F \sqcup F'\) stand for any other set obtained from \(F \cup F'\) by replacing one or more clauses \(C\) of \(F\) by \(x \cup C\) and one or more clauses \(C'\) of \(F'\) by \(\bar{x}\cup C'\), where \(x\) is a new variable; then \(F \sqcup F'\) is unsatisfiable whenever \(F\) and \(F'\) are both unsatisfiable. For example, if \(F = \{\varepsilon\}\) and \(F' = \{1, \bar{1}\}\), then \(F \sqcup F'\) is either \(\{2, 1\bar{2}, \bar{1}\bar{2}\}\) or \(\{2, 1, \bar{2}\}\) or \(\{2, 1\bar{2}, \bar{1}\}\).

    (c): At least three of the variables will have forced values.