Complexity

Polynomial Time

The class of all decision problems computable by a turing machine in polynomial time with respect to the size of the input.

Non-Deterministic Polynomial Time

The class of all decision problems for which a "yes" answer can be verified in polynomial time with respect to the size of the input

Complement Non-Deterministic Polynomial Time

A decision problem

X

is a member of co-NP if and only if it's complement is in

𝒩 𝒫

Non-Deterministic Polynomial Time Hard

A computation problem

H

is called NP-hard if for every problem

L \in 𝒩 𝒫

, there is a polynomial time reduction from

L

H

Adding to Reduce

A 3-dimensional matching is a problem defined as follows: Let

X, Y, Z

be finite sets of natural numbers (could be multi-sets), and let

| X | = | Y | = | Z | = n

. We say

M

is a 3-dimensional matching if

$M \subseteq {(x, y, z) : x \in X, y \in Y, z \in Z}$
for any $𝒮 \in {X, Y, Z}$ each element $s \in S$ , it appears in exactly one triplet $(x, y, z) \in M$ ,
sum of every triplet $x + y + z$ is the same
$| M | = n$

Let 3DM be the decision version of 3-dimensional matching that given the sets $X, Y, Z$ , decide whether there exists a 3-dimensional matching $M$ satisfying the properties above. An instance of 3DM is defined as $⟨ X, Y, Z ⟩$ .

Let XYL be the decision problem that given two sets of natural numbers $X$ and $Y$ (they can be multi-sets, too) where $| X | = n$ and $| Y | = 2 n$ and decide if it is possible to form $n$ triples $(x_{i}, y_{j}, y_{k})$ such that $x_{i} \in X$ and $y_{j}, y_{k} \in Y$ and all the triples have the same sum, and each element is used exactly once. An instance of XYL is defined as $⟨ X, Y ⟩$ .

It is well-known that 3DM is $𝒩 𝒫$ -complete, show that $𝖷 𝖸 𝖫$ is $𝒩 𝒫$ -complete.

Hint: what if you add a big number to every element in $Y$ (or $Z$ or both)?

In order to prove that XYL is NP complete, we will use a karp reduction. Firstly let's note that XYL is in NP, this is true because given a collection of $n$ triples satisfying the constraints, we can easily verify that they all have the correct properties in polynomial time with respect to the size of the input.

Now moving to the reduction, what we must do is to take an instance of 3DM and in polynomial time, we must construct an instance of XYL, and then prove that the answer to 3DM is yes if and only if the answer to XYL is yes.

Suppose we have an instance $⟨ X, Y, Z ⟩$ of 3DM, let $f (z) : = \max (X) + 2 \max (Y) + \max (Z) + z$ and define $Z : = {z + f (z) : z \in Z}$ , we construct the instance of XYL by using $⟨ X, Y ⊔ Z ⟩$ . $⟹$ Now suppose that the answer to 3DM with the instance $⟨ X, Y, Z ⟩$ is yes, therefore we have the set $M$ satisfying all the properties listed in the question. Since we get $n$ triples, then for any two triples of the form $(x_{i}, y_{j}, z_{k})$ , $(x_{l}, y_{m}, z_{n})$ we know that $x_{i} + y_{j} + z_{k} = x_{l} + y_{m} + z_{n}$ , therefore we conclude also that $x_{i} + y_{j} + f (x_{k}) = x_{l} + y_{m} + f (z_{n})$ this is because applying $f$ simply just adds a constant to each side, but we observe that the triples $(x_{i}, y_{j}, f (z_{k}))$ and $(x_{l}, y_{m}, f (z_{n}))$ are arbitrary triples in $⟨ X, Y ⊔ Z ⟩$ having the same sum and there are exactly $n$ of these triples (by mapping the original ones through $f$ ), thus we've just shown there are $n$ triples all having the same value using each value exactly once (since $f$ is an injection). So the answer to XYL is yes.

$⟸$ Suppose that the answer to XYL is yes, so that we have $n$ tuples using each value exactly once, and all having the same sum. Without further inspection it seems that a tuple of the form $x_{i}, y_{j}, y_{k}$ or $x_{i}, z_{j}, z_{k}$ may be possible to exist within the $n$ tuples, but we will actually prove that specifically it must be of the form $x_{i}, y_{j}, z_{k}$ , that is to say, we cannot use two elements of $Y$ nor two elements of $Z$ as part of any tuple.

With $n$ different tuples, we must have that each that each element of $Y ⊔ Z = 2 n$ is used exactly once, if they were not they we wouldn't not be able to form $n$ tuples or if we go over, one of them would be duplicated. Now, there are two situations, either there will exist a tuple of the form $x_{i}, y_{j}, y_{k}$ or $(x_{i}, z_{j}, z_{k})$ or else they will all be of the form $(x_{i}, y_{j}, f (z_{k}))$ (up to a re-ordering) .

In the initial case of $(x_{i}, y_{j}, y_{k})$ , we observe that $f (z_{k}) > x_{i} + y_{j} + y_{k}$ by the definition of $f$ , but since $f (x_{k})$ will exist in exactly one tuple (or else we cannot create $n$ tuples), then clearly this specific tuple will have a sum which is greater and thus not equal to the sum of $(x_{i}, y_{j}, y_{k})$ , which contradictions our assumption that XYL answers yes.

Similarly suppose there is a triple of the form $(x_{i}, z_{j}, z_{k}) = (x_{i}, f (z_{j}), f (z_{k}))$ , since another tuple of the form $(x_{l}, y_{m}, y_{n})$ cannot exist as just noted, then there must be a tuple of the form $(x_{l}, y_{m}, f (z_{n}))$ , we'll note

\begin{matrix} x_{i} + f (z_{j}) + f (z_{k}) & a m p; = x_{i} + (\max (X) + 2 \max (Y) + \max (Z) + 1 + z_{j}) + (\max (X) + 2 \max (Y) + \max (Z) + 1 + z_{k}) \\ a m p; = 2 \max (X) + 4 \max (Y) + 2 \max (Z) + 2 + (x_{i} + z_{j} + z_{k}) \end{matrix}

and then a chain of inequalities

\begin{matrix} x_{l} + y_{m} + f (z_{n}) & a m p; \leq \max (X) + \max (Y) + (\max (X) + 2 \max (Y) + \max (Z) + 1 + z_{n}) \\ a m p; = 2 \max (X) + 3 \max (Y) + \max (Z) + 1 + z_{n} \\ a m p; \leq 2 \max (X) + 3 \max (Y) + 2 \max (Z) + 1 \\ a m p; \leq 2 \max (X) + 4 \max (Y) + 2 \max (Z) + 1 \\ a m p; < 2 \max (X) + 4 \max (Y) + 2 \max (Z) + 2 + (x_{i} + z_{j} + z_{k}) \\ a m p; = x_{i} + f (z_{j}) + f (z_{k}) \end{matrix}

Therefore we've found two tuples which have different value within they $n$ tuples that supposedly all had the same value which is a contradiction, so every tuple is of the form $(x_{i}, y_{j}, f (z_{k}))$ . With that said there is a simple injective mapping which takes this tuple to the tuple $(x_{i}, y_{j}, z_{k})$ , which is a valid element of 3DM, we also note that if $x_{i} + y_{j} + f (x_{k}) = x_{l} + y_{m} + f (x_{n})$ then we know that $x_{i} + y_{j} + z_{k} = x_{l} + y_{m} + z_{n}$ as the function only adds a constant to each side. Therefore by using this injective mapping, we produce $n$ tuples for 3DM, each of which have the same sum, and since the tuples in XYL used each element exactly once, then this property also holds when in 3DM, therefore these $n$ tuples form a 3-dimensional matching and so the answer to 3DM is yes, as needed.

Thus we know that XYL is in NP and we've found a reduction from an NP-complete problem to it, thus we can conlude that XYL is NP-complete as needed.

We say a boolean formula is a four-occurrence CNF formula if it is in conjunctive normal form and every variable appears at most four times. Define

{𝖢 𝖭 𝖥}_{4} = {ψ : ψ is a satisfiable, four-occurrence CNF formula} .

It is well-known that

{𝖢 𝖭 𝖥}_{𝟦}

𝒩 𝒫

-complete. Now we define a boolean formula to be a four-occurrence 4CNF formula if it is in conjunctive normal form, and every variable appears at most four times, and every clause contains exactly four literals (no repetitions). Define

{𝟦 𝖢 𝖭 𝖥}_{4} = {ϕ : ϕ is a satisfiable, four-occurrence 4CNF formula} .

Which complexity class is

{𝟦 𝖢 𝖭 𝖥}_{𝟦}

in? Is it in

𝒫

? Is it in

𝒩 𝒫

? Is it

𝒩 𝒫

-complete? You need to answer each question and prove your solution.

We'll show that ${𝟦 𝖢 𝖭 𝖥}_{𝟦} \in 𝒫$ , since $𝒫 \subseteq 𝒩 𝒫$ , if it was NP-hard, then $P = N P$ which we assume is false, so we know that cannot be the case.

To show it's in $𝒫$ we must construct a polynomial time solution with respect to the size of the input. Before we do this we'll note the following:

Suppose that we have some formula $ϕ$ that has $k$ clauses and $n$ varaibles, construct a bi-partite graph by putting a node for each clause on the left, and then a node for each varaible on the right. Connect from left to right by taking some clause $c_{i}$ and then connecting it to every varaible used in that clause. Note that a perfect matching in this graph induces a valid truth assignment, this is because in the matching every variable is assigned to some clause, and so for those varaibles we set them to be true, if the negation of that variable is used in the clause set it to false. This means that at least one term in the clauses evaluates to true, since this holds for all clauses the entire statement evaluates to true because of the $\lor, \land$ structure of conjuctive normal form.

Note that this all relies on the fact that we can produce a perfect matching, recall Hall's Marriage theorem which states that you can find a perfect matching for some bi-partite graph $G = (U ⊔ V, E)$ iff for any $S \subseteq U$ , $| N (S) | \geq | S |$ . We'll now focus on showing this property so that we can always find a perfect matching.

Let $S \subseteq C$ such that $| S | = k$ , for each clause in $C$ there are four edges going out into $V$ because each clause uses 4 unique variables, at the same time, for any variable $v \in V$ it has at most $4$ edges going into it this is because each variable is used at most four times. If $| N (S) | < k$ then they could only intake $4 (k - a)$ for some $a \in ℕ_{1}$ incoming edges, but we need them to be able to intake $4 \cdot k$ , which is impossible, and therefore we must have that $| N (S) | \geq | S |$

Therefore we can conclude that there is always a perfect matching, and thus every formula is satisfiable. What this means that there is a polynomial algorithm to answer the decision problem, it simply returns true, and runs in constant time, which is what we need for our initial paragraph to make sense.

Subset Sum Problem

Given a finite subset

X \subseteq ℤ

and some integer

W

is there a subset

S \subseteq X

whose sum equals

W

Subset Sum is in NP

As per title.

Given a subset, we can simply iterate over all of its values each time adding that value to an incrementing sum, after finitely many iterations we can answer yes or if if that sum equals

W

Subset Sum is NP-Complete

As per title.

Reduce exact 3sat to subset sum

Set Partition Problem

Suppose

X \subseteq ℤ

such that

| X | = n

. Does there exist a partition of

X

into two sets with equal sum?

For example given the set $X = {2, 3, 4, 8, 1}$ then we can take the subsets ${2, 3, 4}$ and ${8, 1}$ where both have sum $9$ . So the answer is yes. For ${2, 3, 4, 7}$ in this case you cannot, so the answer is no.

Set Partition is in NP

As per title.

Given a proposed solution

A, B

we have to verify that the sum of both subsets are equal and that they form a partition of

X \subseteq ℤ

, which we can do by showing that

A \cup B = X

and

A \cap B = \emptyset

. Which can be done in polynomial time

Set Partition is NP-Complete

As per title.

We will do a karp reduction to show that $SubsetSum \leq_{p} SetPartition$ . Suppose we are given an instance of subset sum, so that we have some finite set $X \subseteq ℤ$ and a target value $T$ , and we want to construct an instance of set partition such that it will answer yes iff subset sum answers yes.

Recall that if set partition finds a solution, then the value that both partitions sum to is exactly half that of the original set. We can use this to our advantage.

Squared Sum Partition

Given positive integers

b_{1}, \dots, b_{n}, j

and

W

, the squared sum partition problem asks whether

{1, \dots, n}

can be partitioned into

j

pairwise disjoint subsets

{1, \dots, n} = C_{1} ⊔ \dots ⊔ C_{j}

, such that

\sum_{i = 1}^{j} {(\sum_{k \in C_{i}} b_{k})}^{2} \leq W

Squared Sum Partition is NP-Complete

As per title.

We do a reduction from set partition. Suppose that ${x_{1}, \dots x_{n}} = X \subseteq ℤ$ , which then is an instance of set partition, and let $T : = \sum X$ . We construct an instance of squared sum partition with $k = 2$ and $W = \frac{T^{2}}{2}$ with integers $x_{1}, \dots x,_{n}$

$⟹$ Suppose that $A, B$ is a solution to the set partition problem, therefore $\sum A = \sum B = \frac{T}{2}$ , therefore we have that ${(\sum A)}^{2} + {(\sum B)}^{2} \leq {(\frac{T}{2})}^{2} + {(\frac{T}{2})}^{2} = \frac{T^{2}}{2} = W$ which shows that squared sum partition holds true.

$⟸$ Suppose that $C_{1}, C_{2}$ is a solution to the squared sum partition problem, so we have that ${(\sum C_{1})}^{2} + {(\sum C_{2})}^{2} \leq \frac{T^{2}}{2}$ for the sake of contradiction let's assume that $\sum C_{1} \neq \sum C_{2}$ , since we know that $\sum C_{1} + \sum C_{2} = T$ since they form a partition then we know that there exists some $ϵ > 0$ such that wlog $\sum C_{1} = \frac{T}{2} + ϵ$ and $\sum C_{2} = \frac{T}{2} - ϵ$ , if that's true then we have $\begin{matrix} {(\sum C_{1})}^{2} + {(\sum C_{2})}^{2} & a m p; = {(\frac{T}{2} + ϵ)}^{2} + {(\frac{T}{2} - ϵ)}^{2} \\ a m p; = (\frac{T^{2}}{4} + T ϵ + ϵ^{2}) + (\frac{T^{2}}{4} - T ϵ + ϵ^{2}) \\ a m p; = \frac{T^{2}}{2} + 2 ϵ^{2} \end{matrix}$ and this is a contradiction because we require that ${(\sum C_{1})}^{2} + {(\sum C_{2})}^{2} \leq \frac{T^{2}}{2}$ , therefore we must have that $\sum C_{1} = \sum C_{2}$ which means that set partition holds true.

Max Cut Problem

Input: An undirected graph $G = (V, E)$ and an integer $ℓ$ .
Question: Is there a partition of $V$ into $(A, B)$ such that at least $ℓ$ edges have one endpoint in $A$ and the other in $B$ ?

Max 2 Sat Problem

Input: A 2-CNF formula $φ$ and an integer $t$ . (In a 2-CNF formula, each clause has exactly two literals.)
Question: Does there exist a truth assignment under which at least $t$ clauses of $φ$ are satisfied?

Max-2-Sat is NP-Complete

Show that MAX-2-SAT is NP-complete. For the hardness part, use MAX-CUT in your reduction. (You can assume that MAX-CUT is known to be NP-complete.)

Max-2-sat is in NP because given a truth assignment we just verify that at least $t$ clauses of $ϕ$ hold true which can be done in polytime.

Next we'll make a reduction starting with an instance of max-cut $(G, ℓ)$ . Start by making variables $x_{u}$ for each $u \in V$ and for each edge $(a, b) \in E$ we create the clauses $x_{a} \lor x_{b}$ and $x_{a} \lor x_{b}$ .

We'll next show that for each cut, we can define a unique truth assignment associated with it. To do this if we have the cut $A, B$ having a cut with $k \geq ℓ$ edges. Then we simply construct the assignment $v (x_{i}) = T ⟺ x_{i} \in A$ . Then for each edge $(j, k)$ in the cut,

Note that we can partition all edges of $E$ into those that are entirely contained in $A$ : $E_{A}$ ( $E_{B}$ respectively) and those which are part of the cut $E_{C}$ . For every edge $(u, v) \in E_{A}$ we see that $v ((x_{u} \lor x_{v})) = T$ whereas $v (x_{u} \lor x_{v}) = F$ , symetrically we see that for any $(m, n) \in E_{B}$ we have that $v (x_{m} \lor x_{n}) = F$ and $v (x_{m} \lor x_{n}) = T$ .

On the other hand for every $(j, k) \in E_{C}$ we see that $v (x_{j} \lor x_{k}) = T \lor F = T = F \lor T = v (x_{j} \lor x_{k})$ . Which is to say that the number of satisfied clauses is given by $| E_{A} | + | E_{B} | + 2 | E_{C} | = | E | + k$

$⟹$ Therefore by using $ϕ$ which is the disjunction of all of the edge clauses, and with $t = | E | + k$ we clearly can say that max-2-sat is satisifed.

$⟸$ On the other hand given $ϕ$ and it's assignment we get a unique cut with at least $k = t - | E |$ edges involved in the cut.