Hints

Green section

Recall the problems:

\[\text{SAT} = \{\braket{\phi} \mid \text{$\phi$ has at least one satisfying assignments}\}\]

and

\[\text{DOUBLE-SAT} = \{\braket{\phi} \mid \text{$\phi$ has at least 2 satisfying assignments}\}\]

Q1

Solving SAT using truth tables

QHintPython

For the following Boolean formulae, count how many satisfying assignments they have, then decide if they are in SAT and DOUBLE-SAT?

• \(\phi_1 = x\land (y\lor \bar x)\land (z\lor \bar y)\)

• \(\phi_2 = (x\lor y)\land\big((\overline{x\lor z})\lor(\bar z\land \bar y)\big)\)

• \(\phi_3 = (\bar x \lor y \lor z) \land (x \lor \bar y \lor z) \land (x \lor y \lor \bar z)\)

Truth tables:

\[\begin{array}{|ccc||c|c|c|} \hline x & y & z & \phi_1 & \phi_2 & \phi_3 \\ \hline\hline 0 & 0 & 0 & 0 & 0 & ... \\ 0 & 0 & 1 & 0 & 0 & ... \\ 0 & 1 & 0 & 0 & 1 & ... \\ 0 & 1 & 1 & 0 & 0 & ... \\ 1 & 0 & 0 & 0 & ... & ... \\ 1 & 0 & 1 & 0 & ... & ... \\ ... & ... & ... & ... & ... & ... \\ ... & ... & ... & ... & ... & ... \\ \hline \end{array}\]

• \(\phi_1\) has only 1 satisfying assignment so

  • \(\braket{\phi_1}\in \text{SAT}\)
  • \(\braket{\phi_1}\not\in\text{DOUBLE-SAT}\)

• \(\phi_2\) has ....... satisfying assignments so

  • \(\braket{\phi_2}\in \text{SAT}\)
  • \(\braket{\phi_2} ....... \text{DOUBLE-SAT}\)

• \(\phi_3\) has ......... satisfying assignments so

  • \(\braket{\phi_3} ....... \text{SAT}\)
  • \(\braket{\phi_3} ....... \text{DOUBLE-SAT}\)

If you like coding then you can try something like:

print("x y z | ϕ1 ϕ2 ϕ3 |")

for x in [0,1]:
    for y in [0,1]:
        for z in [0,1]:
            phi1 = x and (y or not x) and (z or not y)
            phi2 = (x or y) and (not(x or z) or (not z and not y))
            phi3 = (not x or y or z) and (x or not y or z) and (x or y or not z)
            phi1 = int(phi1)
            phi2 = int(phi2)
            phi3 = int(phi3)
            print("{} {} {} | {}  {}  {}  |".format(x,y,z,phi1,phi2,phi3))

Q2

Proving that TRIPLE-SAT is NP-complete

QVideo

Define

\[\text{TRIPLE-SAT} = \{\braket{\phi} \mid \text{$\phi$ has at least 3 satisfying assignments}\}\]

Complete the proof below to show that \(\text{TRIPLE-SAT}\) is NP-complete.

Proof

We need to show that \(\text{TRIPLE-SAT}\in\textbf{NP}\) ....... \(\text{SAT}\leq_P \text{TRIPLE-SAT}\).

[½] \(\text{TRIPLE-SAT}\in\textbf{NP}\):

On input \(\braket{\phi (x_1,\dots,x_n)}\), non-deterministically guess .... different for the Boolean variables \(x_1,\dots,x_n\), and verify whether they all ........ \(\phi\).

The verification step only costs \(O( ........ )\).

[2/2] \(\text{SAT}\leq_P \text{TRIPLE-SAT}\):

On input \(\braket{\phi (x_1,\ldots,x_n)}\), introduce 2 new Boolean variables \(a\) and \(b\), and output the formula: \(\(\Psi(x_1,\ldots,x_n, a, b) = \phi (x_1,\ldots,x_n)\,\land (a\lor b).\)\)

• (½) If \(\braket{\phi}\in\text{SAT}\) then this means that \(\phi\) has at least ...... satisfying assignment, and therefore \(\phi\,\land (a\lor b)\) has at least ....... satisfying assignments because the added clause \((a\lor b)\) can be satisfied in 3 ways:

  \[(a,b)\in\{(1,0), (0,1), (....,....)\}.\]

  So \(\braket{\Psi} = \braket{\phi\,\land (a\lor b)} \in \text{TRIPLE-SAT}\).

• (2/2) If \(\braket{\phi} \not\in \text{SAT}\) then \(\phi \land (a\lor b)\) .......... have a satisfying assignment because

  \[0 \land 0 = 0 \qquad\text{ and }\qquad 0\land ..... = 0.\]

  So \(\braket{\Psi} = \braket{\phi \land (a\lor b)} \not\in \text{TRIPLE-SAT}\).

Therefore, \(\text{SAT}\leq_P \text{TRIPLE-SAT}\), and hence TRIPLE-SAT is NP-complete.

Q3

A slightly different proof that DOUBLE-SSP is NP-complete

Let \(\mathbb{N}= \{1,2,3,\ldots\}\) be the set of natural numbers, and define

\[\mathbb{N}_t = \{n\in\mathbb{N}\mid n<t\} \qquad\qquad (\text{i.e. }\mathbb{N}_t= \{1,2,\ldots,t-1\})\]

Consider the following restricted version of the Subset-Sum Problem (SSP)

\[\begin{array}{rcl} \text{SSP}= \{\braket{\mathcal{S},t} &\mid& \text{$\mathcal{S}\subsetneq \mathbb{N}_t$ is a finite set, and $t\in\mathbb{N}$, such that} \\ && \text{there is a subset of $\mathcal{S}$ whose sum is $t$}\} \end{array}\]

Here the notation "\(A\subsetneq B\)" means that \(A\subset B\) but \(A\neq B\).

SSP is NP-complete.

Define:

\[\begin{array}{rcl} \text{DOUBLE-SSP}= &\{&\braket{\mathcal{S},t} \mid \text{$\mathcal{S}\subset\mathbb{N}_t$ is a finite set, and $t\in\mathbb{N}$, such that } \\ && \text{there are two distinct subsets of $\mathcal{S}$ which both sum to $t$}\} \end{array}\]

Complete the proof below to show that \(\text{DOUBLE-SSP}\in \textbf{NP-complete}\).

Proof

[½] \(\text{DOUBLE-SSP}\in {\textbf{NP}}\) because we can ........ if 2 given subsets \(\mathcal{T}_1, \mathcal{T}_2\) of \(\mathcal{S}\) sum to \(t\) and check that \(\mathcal{T}_1\neq \mathcal{T}_2\) in time \(O(.......)\), which is polynomial time.

[2/2] \(\text{SSP}\leq_P \text{DOUBLE-SSP}\).

Since \(\mathcal{S}\subsetneq \mathbb{N}_t\) then \(\mathcal{S}\) ........ at least an element \(m\) from \(\{1,2,3,\ldots, t-1\}\). Select such an \(m\) and build a  instance \(\braket{\mathcal{S}',t}\) where\(\mathcal{S}'=\mathcal{S}\;\cup\;\{m,t-m\}.\)

• (½) Showing that: \(\braket{\mathcal{S}, t}\in \text{SSP}\implies \braket{\mathcal{S}', t} .... \text{DOUBLE-SSP}\).

  Since \(\braket{\mathcal{S}, t}\in \text{SSP}\) then there is a subset \(\mathcal T\subset \mathcal{S}\) which ...... to \(t\).

  A second solution is given by ........

• (2/2) Showing that: \(\braket{\mathcal{S}', t}\in \text{DOUBLE-SSP}\implies \braket{\mathcal{S}, t}\in .....\).

  If \(\braket{\mathcal{S}', t}\in \text{DOUBLE-SSP}\) then there are two distinct subsets \(\mathcal T\) and  \(\mathcal U\) of \(\mathcal{S}'\) that both sum to \(t\).

  \(\mathcal T\) and \(\mathcal U\) cannot both be \(\{m,t-m\}\) because they must be ......... So one of them must be a ........ of \(\mathcal{S}\).

  So, \(\braket{\mathcal{S}, t}\in \text{SSP}\).

Q4

The CLIQUE problem

QHint

Consider the following graph:

and recall that

\[\text{CLIQUE} = \{\braket{G,k} \mid \text{The graph $G$ has a $k$-clique}\}\]

• What is the largest \(k\) for which this graph satisfies CLIQUE?

• In general, how many edges does a \(k\)-clique have (as a function of \(k\))?

• There are two triangles (3-cliques): \(\{1,2,3\}\) and \(\{2,3,4\}\). However, there is no 4-clique, since there are only 4 nodes, and one edge is missing.

  Thus \(k = ...\) is the answer.

• All pairs of nodes must have an edge between them, and the number of pairs of \(k\) nodes is

  \[{k \choose 2} = \frac{k!}{2!(k-2)!} = \frac 12 k(k-1).\]

Counting...

The number of choosing \(k\) elements from \(n\) elements is

\[{n\choose k} = \frac{n!}{k!(n-k)!} = \frac{1}{k!} \cdot n\cdot (n-1)\cdots (n-k+1).\]

We read this as "\(n\) choose \(k\)."

You can learn more about it at https://en.wikipedia.org/wiki/Combination

Q5

The VERTEX-COVER problem

QHintDetails

A vertex cover of an undirected graph \(G\) is a subset of the vertices where every edge of \(G\) touches one of those vertices.

The VERTEX-COVER problem asks whether a graph contains a vertex cover of a specified size:

\[\text{VERTEX-COVER} = \{\braket{G, k} \mid \text{$G$ is an undirected graph that has a $k$-vertex cover}\}.\]

What is the smallest \(k\) for which the graph from the previous question satisfies VERTEX-COVER?

\(k=2\)

Q6

The HAMILTONIAN-CIRCUIT problem

QHints

Do the following graphs have Hamiltonian circuits?

• Yes for the first one, e.g. 0-1-11-12-2-3-13-14-4-5-15-............

• No for the second.

  To visit 6 we must have 0 and 3 as its immediate neighbours. This forces the inclusion of the path 0-6-3 and makes it impossible to visit .......

  Another way to also see it is to realise that we must have the paths 0-1-2-3 and 0-5-4-3. This makes it impossible to create a hamiltonian cycle that also includes ........

• No for the third. (The proof is a little more involved... and you were not asked for proofs)

Orange section

Q7

Proving that 3SAT is NP-complete

Let \(x_1,x_2,\ldots,x_n\) be Boolean variables, and let \(\phi\) be a Boolean formula written in 3-cnf (Conjunctive Normal Form, like \(\phi_3\) in the first exercise) given by

\[\phi = c_1\land c_2\land \cdots \land c_\ell,\]

where each clause \(c_m\) has the form \(\alpha\lor \beta \lor \gamma\), where each of \(\alpha, \beta, \gamma\) is a literal: a variable \(x_i\) or its negation \(\bar x_i\).

The 3SAT problem is NP-complete, and asks if a given 3-cnf formula is satifiable.

We showed in the lecture that the Subset-Sum Problem (SSP) is in P. Now, show that SSP is NP-complete by reducing 3SAT to it, i.e. show that

\[\text{3SAT}\leq_P \text{SSP}\]

You may find it easier if you study the discussion at https://saravananthirumuruganathan.wordpress.com/2011/02/07/detailed-discussion-on-np-completeness-of-subset-sum/ then the proof given in the textbook.

Q8

Proving that CLIQUE is NP-complete

QHint

Prove that CLIQUE is NP-complete by reducing the VERTEX-COVER problem to CLIQUE. (VERTEX-COVER is NP-complete)

You can use the following reduction from VERTEX-COVER to CLIQUE:

Suppose we are given an instance \(\braket{G,k}\) of VERTEX-COVER. Construct the instance \(\braket{G',n-k}\) of CLIQUE, where \(n\) is the total number of nodes of \(G\), and \(G'\) is \(G\) with the set of edges complemented (i.e. \(G'\) has an edge if and only if \(G\) does not have that edge).

We must show that \(G\) has a node cover of size \(k\) if and only if \(G'\) has a clique of size \(n-k\).

• First, let \(C\) be a node cover of \(G\) of size \(k\). We claim that \(C'\), the complement of the nodes in \(C\), is a clique in \(G'\) of size \(n-k\).

  Surely \(C'\) is of size ..... Suppose it is not a clique. Then there is a pair of nodes \((u,v)\) that do not have an edge in \(G'\). Thus this edge is in \(G\). But neither \(u\) nor \(v\) is in \(C\), contradicting the assumption that is is a node cover.

• Conversely, if \(C'\) is a clique of size \(n-k\) in \(G'\), then we claim that \(C\) the complement of \(C'\), is a node cover of size \(k\) in \(G\).

  The argument is similar: if \((u,v)\) is an edge of \(G\) not covered by \(C\), then both \(u\) and \(v\) are in ........, but the edge \((u,v)\) is not in \(G'\), contradicting the assumption that \(C'\) is a clique.

Q9

Proving that HALF-CLIQUE is NP-complete

QHintDetails

Given a graph \(G\) with an even number of vertices \(n\), does \(G\) have an \(n/2\)-clique?

Reduce CLIQUE to HALF-CLIQUE.

You need to figure out how to add vertices to adjust the size of the largest clique depending on whether \(k=n/2\) or \(k>n/2\) or \(k<n/2\) (e.g., if \(k = n/2\), just produce \(G\)).

Let \((G,k)\) be an instance of CLIQUE, and suppose \(G\) has \(n\) vertices. We produce an instance of the HALF-CLIQUE, as follows:

• If \(k = n/2\), just produce \(G\).

  Note that \(G\) has a half-clique if and only if it has a clique of size \(k\) in this case.

• If \(k > n/2\), add \(2k - n\) isolated vertices (vertices with no incident edges).

  The resulting graph has a half-clique (whose size must be \((n + (2k-n))/2 = 2k\), if and only if \(G\) has a clique of size .......

• If \(k < n/2\), add \(n - 2k\) vertices, and connect them in all possible ways to each other and to the original vertices of \(G\).

  The new graph thus has ......... vertices. The new vertices, plus a clique of size \(k\) in \(G\) form a clique of size \((n-2k) + k = n-k\), which is half the number of vertices in the new graph.

  Conversely, if the new graph has a half-clique, then it must include at least \((n-k) - (n-2k) = k\) vertices of the graph \(G\), implying that \(G\) has a clique of size ........

These steps complete a reduction of CLIQUE to HALF-CLIQUE. It is evidently performable in polynomial time, since the number of new vertices and edges is at most the square of the original number of vertices, and the rules for adding vertices and edges are simple to carry out.

Q10

Showing that P is closed under union, concatenation and complementation

QUnionConcatenationComplementation

Show that the class P is closed under:

• Union.
• Concatenation.
• Complementation.

Test for membership in one language and then, if the input is not in the first, test for membership in the second.

The time taken is no more than the ....... of the times taken to recognize each language.

Since both are in ........, then each can be recognized in ........ time, and the sum of polynomials is a polynomial.

Thus, their union is in P.

Let \(L_1\) and \(L_2\) be languages in P, and suppose we want to recognize their concatenation.

The idea is to try all the possible ways in which we can split the string into a concatenation of 2 strings from the given languages.

The running time of this test is at most \(n\) times the sum of the running times of the recognizers for \(L_1\) and \(L_2\).

Since the latter are both polynomials, so is the running time for the TM just described.

Given a polynomial-time TM \(M\) for \(L\), we construct a TM \(M'\) that decides \(\overline L\) (the complement of \(L\)) as follows:

• On input \(w\):
• Run \(M\) on \(w\).
• If \(M\) accepts, ........; if \(M\) rejects, ........

Since \(M'\) does the opposite of whatever \(M\) does then it decides \(\overline L\).

Furthermore, \(M'\) also runs in polynomial time because it only needs one extra step after \(M\) .........

(Alternative approach: Simply swap the accept and reject state. The running time of the modified machine does not change. )