Homework 13

Problem 1.

The Set Partition Problem takes as input a set $S$ of numbers. The question is whether the numbers can be partitioned into two sets $A$ and $\bar{A}=S-A$ such that
$$\sum_{x \in A} x=\sum_{x \in \bar{A}} x$$
Show that SET-PARTITION is NP-Complete. (Hint: Reduce SUBSET-SUM.)

Proof .

To show that any problem $A$ is NP-Complete, we need to show four things:
(1) there is a non-deterministic polynomial-time algorithm that solves $A$, i.e., $A \in \mathrm{NP}$,
(2) any NP-Complete problem $B$ can be reduced to $A$,
(3) the reduction of $B$ to $A$ works in polynomial time,
(4) the original problem $A$ has a solution if and only if $B$ has a solution.
We now show that SET-PARTITION is NP-Complete.
(1) SET-PARTITION $\in \mathrm{NP}$ : Guess the two partitions and verify that the two have equal sums.
(2) Reduction of SUBSET-SUM to SET-PARTITION: Recall SUBSET-SUM is defined as follows: Given a set $X$ of integers and a target number $t$, find a subset $Y \subseteq X$ such that the members of $Y$ add up to exactly $t .$ Let $s$ be the sum of members of $X$. Feed $X^{\prime}=X \cup{s-2 t}$ into SET-PARTITION. Accept if and only if SET-PARTITION accepts.
(3) This reduction clearly works in polynomial time.
(4) We will prove that $\langle X, t\rangle \in$ SUBSET-SUM iff $\left\langle X^{\prime}\right\rangle \in$ SET-PARTITION. Note that the sum of members of $X^{\prime}$ is $2 s-2 t$.
$\Rightarrow:$ If there exists a set of numbers in $X$ that sum to $t$, then the remaining numbers in $X$ sum to $s-t$. Therefore, there exists a partition of $X^{\prime}$ into two such that each partition sums to $s-t$.
$\Leftarrow$ : Let’s say that there exists a partition of $X^{\prime}$ into two sets such that the sum over each set is $s-t$. One of these sets contains the number $s-2 t$. Removing this number, we get a set of numbers whose sum is $t$, and all of these numbers are in $X$.

Problem 2.

Let
DOUBLE-SAT $={\langle\phi\rangle \mid \phi$ is a Boolean formula $}$.
1
Show that DOUBLE-SAT is NP-Complete. (Hint: Reduce $3 S A T$.)

Proof .

(1) DOUBLE-SAT $\in \mathrm{NP}$ : Simply guess two different assignments to all variables and verify that each clause is satisfied in both cases.
(2) Reduction of $3 S A T$ to DOUBLE-SAT: Given a 3 cnf-function $\psi$, create a new Boolean function $\psi^{\prime}$ by adding a new clause $(x \cup \bar{x})$ to $\psi$, where $x$ is a new variable not in $\psi$. Then check if $\left\langle\psi^{\prime}\right\rangle \in D O U B L E-S A T$.
(3) This reduction clearly works in polynomial time.
(4) We now prove that the original 3 cnf-function $\langle\psi\rangle \in 3 S A T$ iff the new Boolean function $\left\langle\psi^{\prime}\right\rangle \in D O U B L E-S A T .$ If the original 3 cnf-function $\psi$ is unsatisfiable, then the new function $\psi^{\prime}$ is also unsatisfiable; i.e., $\langle\psi\rangle \notin 3 S A T$ implies $\left\langle\psi^{\prime}\right\rangle \notin$ DOUBLE-SAT. If $\langle\psi\rangle \in 3 S A T$, then use the same assignment of variables that are in $\psi$, and we also have both $x=0$ and $x=1$ are valid assignments. Thus, there are at least two satisfying assignments of the augmented 3 cnf-formula $\psi^{\prime}$, so $\left\langle\psi^{\prime}\right\rangle \in D O U B L E-S A T$.

Problem 3.

Let $G$ represent an undirected graph. Also let
$S P A T H={\langle G, a, b, k\rangle \mid G$ contains a simple path of length at most $k$ from $a$ to $b}$ and
$L P A T H={\langle G, a, b, k\rangle \mid G$ contains a simple path of length at least $k$ from $a$ to $b}$
(a) Show that $S P A T H \in \mathrm{P}$.
The marking algorithm for recognizing $P A T H$ can be modified to keep track of the length of the shortest paths discovered. Here is a detailed description of the algorithm.
“On input $\langle G, a, b, k\rangle$ where $m$-node graph $G$ has nodes $a$ and $b$ :

1. Place a mark “0” on node $a$.
2. For each $i$ from 0 to $m$ :
3. If an edge $(s, t)$ is found connecting $s$ marked ” $i$ ” to an unmarked node $t$, mark node $t$ with ” $i+1 “$
4. If $b$ is marked with a value of at most $k$, accept. Otherwise, reject.
(b) Show that $L P A T H$ is NP-Complete. You may assume the NP-completeness of UHAMPATH, the Hamiltonian path problem for undirected graphs.

Problem 1.

The Set Partition Problem takes as input a set $S$ of numbers. The question is whether the numbers can be partitioned into two sets $A$ and $\bar{A}=S-A$ such that
$$\sum_{x \in A} x=\sum_{x \in \bar{A}} x$$
Show that SET-PARTITION is NP-Complete. (Hint: Reduce SUBSET-SUM.)

Proof .

First, $L P A T H \in \mathrm{NP}$ because we can guess a simple path of length at least $k$

from $a$ to $b$ and verify it in polynomial time. Next $U H A M P A T H \leq_{\mathrm{P}} L P A T H$, because the following TM $F$ computes the reduction $f$.
$F=$ “On input $\langle G, a, b\rangle$ where graph $G$ has nodes $a$ and $b:$

1. Let $k$ be the number of nodes of $G$.
2. Output $\langle G, a, b, k\rangle$.
If $\langle G, a, b\rangle \in U H A M P A T H$, then $G$ contains a Hamiltonian path of length $k$ from $a$ to $b$, so $\langle G, a, b, k\rangle \in L P A T H .$ If $\langle G, a, b, k\rangle \in L P A T H$, then $G$ contains a simple path of length $k$ from $a$ to $b .$ But $G$ has only $k$ nodes, so the path is Hamiltonian. Thus, $\langle G, a, b\rangle \in U H A M P A T H$.

real analysis代写analysis 2, analysis 3请认准UprivateTA™. UprivateTA™为您的留学生涯保驾护航。

Categories: 未分类