Chapter_34_NP-Completeness/exercises_34.2.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 34.2 Polynomial-time verification"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 34.2-1\n",
    "\n",
    "> Consider the language GRAPH-ISOMORPHISM $ = \\{ \\langle G_1, G_2 \\rangle : G_1$ and $G_2$ are isomorphic graphs$\\}$. Prove that GRAPH-ISOMORPHISM $\\in$ NP by describing a polynomial-time algorithm to verfify the language."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The certificate should be a mapping $f$ that maps $u_1 \\in G_1$ to $u_2 \\in G_2$, which could be an array and the mapping takes $O(1)$ time in a random-access machine.\n",
    "\n",
    "For any $u_1, v_1 \\in G_1$ if there exists an edge in $G_1$ between $u_1$ and $v_1$, then there must exist an edge in $G_2$ that connects $u_2 = f(u_1) \\in G_2$ and $v_2 = f(v_1) \\in G_2$, and vice versa."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 34.2-2\n",
    "\n",
    "> Prove that if $G$ is an undirected bipartite graph with an odd number of vertices, then $G$ is nonhamiltonian."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* starts in even partition: leaves vertices in odd partition unvisited\n",
    "* starts in odd partition: no edge connects two vertices in the same partition"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 34.2-3\n",
    "\n",
    "> Show that if HAM-CYCLE $\\in$ P, then the problem of listing the vertices of a hamiltonian cycle, in order, is polynomial-time solvable."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For every vertex $u \\in V$, let $E_u$ be the set of edges that connects to $u$, enumerate two edges $e_1, e_2 \\in E_u$ until HAM-CYCLE$(\\langle G' = (V, (E - E_u) \\cup \\{e_1, e_2\\}) \\rangle) = 1$ and keep only these two edges (since there exists a hamiltonian cycle that uses the two edges). After removing the edges we can get the order by running a DFS from any vertex."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 34.2-4\n",
    "\n",
    "> Prove that the class NP of languages is closed under union, intersection, concatenation, and Kleene star. Discuss the closure of NP under complement."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Union\n",
    "\n",
    "```\n",
    "IF A_1(x, y) == 1 || A_2(x, y) == 1\n",
    "THEN RETURN TRUE\n",
    "ELSE RETURN FALSE\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Intersection\n",
    "\n",
    "```\n",
    "IF A_1(x, y) == 1 && A_2(x, y) == 1\n",
    "THEN RETURN TRUE\n",
    "ELSE RETURN FALSE\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Concatenation\n",
    "\n",
    "```\n",
    "FOR i = 1 .. n\n",
    "    FOR j = 1 .. m\n",
    "    IF A_1(x_1 ... x_i, y_1 ... y_j) == 1 && A_2(x_i+1 ... x_n, y_j+1 ... y_m) == 1\n",
    "    THEN RETURN 1\n",
    "RETURN 0\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Kleene star\n",
    "\n",
    "```\n",
    "IF x == epsilon\n",
    "THEN RETURN 1\n",
    "\n",
    "FOR i = 1 .. n\n",
    "    FOR j = 1 .. m\n",
    "        DP[i, j] = 0\n",
    "DP[0, 0] = 1\n",
    "FOR i = 0 .. n\n",
    "    FOR j = 0 .. m\n",
    "        FOR k = i + 1 .. n\n",
    "            FOR l = j + 1 .. m\n",
    "        IF A_1(x_i ... x_k, y_j .. y_l) == 1\n",
    "        THEN DP[k, l] = 1\n",
    "RETURN DP[n, m]\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 34.2-5\n",
    "\n",
    "> Show that any language in NP can be decided by an algorithm running in time $2^{O(n^k)}$ for some constant $k$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```\n",
    "FOR all possible y\n",
    "    IF A(x, y) == 1\n",
    "    THEN RETURN 1\n",
    "RETURN 0\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 34.2-6\n",
    "\n",
    "> A __hamiltonian path__ in a graph is a simple path that visits every vertex exactly once. Show that the language HAM-PATH$=\\{\\langle G, u, v \\rangle:$ there is a hamiltonian path from $u$ to $v$ in graph $G\\}$ belongs to NP."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Suppose $G = (V, E)$ and the certificate is the sequence of vertices $\\{v_1, \\dots v_n\\}$, then we should verify:\n",
    "\n",
    "* $ n = |G| $\n",
    "* $ v_1 = u $\n",
    "* $ v_n = v $\n",
    "* $ \\forall i \\in \\{1, \\dots, n\\}, v_i \\in V $\n",
    "* $ \\forall i \\in \\{1, \\dots, n - 1\\}, j \\in \\{i + 1, \\dots, n\\}, v_i \\ne v_j $\n",
    "* $ \\forall i \\in \\{1, \\dots, n - 1\\}, (v_i, v_{i+1}) \\in E $"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 34.2-7\n",
    "\n",
    "> Show that the hamiltonian-path problem from Exercise 34.2-6 can be solved in polynomial time on directed acyclic graphs. Give an efficient algorithm for the problem."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Find the longest path from $u$ to $v$. It is a hamniltonian-path if the length of the path is $|V|$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 34.2-8\n",
    "\n",
    "> Let $\\phi$ be a boolean formula constructed from the boolean input variables $x_1, x_2, \\dots, x_k$, negations($\\neg$), ANDs($\\wedge$), ORs($\\vee$), and parentheses. The formula $\\phi$ is a __tautology__ if it evaluates to 1 for every assignment of 1 and 0 to the input varibales. Define TAUTOLOGY as the lanuage of boolean formulas that are tautologies. Show that TAUTOLOGY $\\in$ co-NP."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The certificate is a set of assignments of 0s and 1s to $x$s. Since it takes $O(n)$ to verify $\\overline{\\text{TAUTOLOGY}}$ by substituting and evaluating the formula and checking whether the result equals to 0, therefore $\\overline{\\text{TAUTOLOGY}}$ $\\in$ NP and TAUTOLOGY $\\in$ co-NP."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 34.2-9\n",
    "\n",
    "> Prove that $\\text{P} \\subseteq \\text{co-NP}$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$\\text{P} \\subseteq \\text{NP}$ (ingores any certificate)\n",
    "\n",
    "$\\overline{\\text{P}} \\subseteq \\text{NP}$ (exercise 34.1-6)\n",
    "\n",
    "$\\text{P} \\subseteq \\text{co-NP}$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 34.2-10\n",
    "\n",
    "> Prove that if $\\text{NP} \\ne \\text{co-NP}$, then $\\text{P} \\ne \\text{NP}$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Prove the contrapositive.\n",
    "\n",
    "Suppose $\\text{P} = \\text{NP}$:\n",
    "\n",
    "* $\\forall L \\in \\text{NP}$ $\\Rightarrow$ $L \\in \\text{P}$ $\\Rightarrow$ $\\overline{L} \\in \\text{P}$ $\\Rightarrow$ $L \\in \\text{co-NP}$\n",
    "* $\\forall L \\in \\text{co-NP}$ $\\Rightarrow$ $\\overline{L} \\in \\text{NP}$ $\\Rightarrow$ $\\overline{L} \\in \\text{P}$ $\\Rightarrow$ $L \\in \\text{P}$\n",
    "*  $\\Rightarrow$ $\\text{NP} = \\text{co-NP}$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 34.2-11\n",
    "\n",
    "> Let $G$ be a connected, undirected graph with at least 3 vertices, and let $G^3$ be the graph obtained by connecting all pairs of vertices that are connected by a path in $G$ of length at most 3. Prove that $G^3$ is hamiltonian."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let $T$ be a spanning tree of $G$, since $T$ has fewer edges than $G$, therefore $T^3$ is hamiltonian $\\Rightarrow$ $G^3$ is hamiltonian.\n",
    "\n",
    "We can prove $T^3$ is hamiltonian by induction:\n",
    "\n",
    "For $|V| = 3$, any permutation forms a hamilton cycle and all edges are used.\n",
    "\n",
    "Suppose $T^3$ is hamiltonian for $|V| < n$, and $u$, $v$ are two vertices connected by an edge $e$ in a $T$ that $|V| = n$.\n",
    "Suppose $u$ and $v$ already belong to two different spanning trees $T_u$ and $T_v$, $|T_u.V| + |T_v.V| = n$. We may assume, with loss of generality, that $|T_u.V| \\ge 3$. Denote one of the vertices connected to $u$ in $T_u$ by $u'$ and one of the vertices connected to $v$ in $T_v$ by $v'$. And through the following constructions we can see there would always exist a hamilton cycle that uses the edge $(u', u)$ ($(\\dots, u, v, \\dots)$ will always be in the hamilton cycle in the construction)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* $|T_v.V| = 1$\n",
    "\n",
    "The distance between $u'$ and $v$ is 2, thus there is an edge $(u', v)$ and we can modity the hamilton cycle in $T_u$ from $(\\dots, u', u, \\dots)$ to $(\\dots, u', v, u, \\dots)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* $|T_v.V| = 2$\n",
    "\n",
    "The distancce between $u'$ and $v'$ is 3, thus there is an edge $(u', v')$ and we can modify the hamilton cycle in $T_u$ and $T_v$ from $(\\dots, u', u, \\dots)$ to $(\\dots, u', v', v, u, \\dots)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* $|T_v.V| \\ge 3$\n",
    "\n",
    "Same as $|T_v.V| \\ge 2$, we can modify the hamilton cycle in $T_u$ and $T_v$ from $(\\dots, u', u, \\dots)$ and $(\\dots, v', v, \\dots)$ to $(\\dots, u', v', \\dots, v, u, \\dots)$. "
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}