$S =$ set of integers

SubsetSum = $\{ (S,t) \mid \exists C \subseteq S\ t=\sum_{x \in C} x\}$

IntPar = $\{ S \mid \exists C \subseteq S\ \sum_{x \in C} x = \sum_{x \in S \setminus C} x\}$

$A = \sum_{x \in S} x$.

IntPar is a special case of SubsetSum, where $t = A/2$.

To show SubsetSum $\leq^P$ IntPar, on input $(S,t)$, we output $S'$ such that $\exists C \subseteq S\ t=$ sum($C$) $\iff \exists C' \subseteq S'$ sum($C'$) = sum($S'$)/2.

If $t =$ sum($S$) / 2, then letting $S'=S$ works.

**Hint:** add an integer to $S$.

Otherwise, we want to add an integer $y$ to $S$ to create $S'$ such that if this $C$ exists, then sum($S'$) / 2. We need $y$ such that sum($S'$) $= 2t$. But sum($S$) $+ y =$ sum($S'$) $=2t$. Solving for $y$, we have $y = 2t -$ sum($S$). Then $\exists C \subseteq S\ t=$ sum($C$) $\iff \exists C' \subseteq S'$ sum($C'$) = sum($S'$)/2.

$(\implies):$ Let $C = C'$, then sum$(C')=$ sum$(C) = t =$ sum$(S')/2$.

$(\impliedby):$ If $y \in C'$, let $C = S' \setminus C'$, otherwise let $C = C'$, so that $C \subseteq S$. Then sum$(C) =$ sum$(C') =$ sum$(S')/2 = t$.

---

Rej$_\infty = \{ M \mid M$ rejects infinitely many inputs $\}$.

def H_e(M):
    def T_M(x):
        M('')
        return False
    return A(T_M)

---

We formalized a decision problem as a subset $L \subseteq \{0,1\}^*$. Equivalently we could formalize a decision problem as a function $f: \{0,1\}^* \to \{0,1\}$, i.e., for all $x \in \{0,1\}^*, x \in L \iff f(x)=1$.

One way to formalize a search problem is as a function $f: \{0,1\}^* \to \{0,1\}^*$, for example, on input $\langle G \rangle \in \{0,1\}^*$, $f(\langle G \rangle) = \langle p \rangle$ where $p$ is a Hamiltonian path in $G$ if it has one, or $f(\langle G \rangle) = w$ otherwise, where $w$ is a string encoding "no Hamiltonian path".

decision algorithm for the related decision problem:

def find_ham_path(G: Graph[Node]) -> list[Node] | False:
    raise NotImplementedError

def ham_path_exists(G) -> bool
    return find_ham_path(G) != False