Chapter_34_NP-Completeness/exercises_34.1.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 34.1 Polynomial time"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 34.1-1\n",
    "\n",
    "> Define the optimization problem LONGEST-PATH-LENGTH as the relation that associates each instance of an undirected graph and two vertices with the number of edges in a longest simple path between the two vertices. Define the decision problem LONGEST-PATH $=\\{\\langle G, u, v, k \\rangle : G = (V, E)$ is an undirected graph, $u, v \\in V$, $k \\ge 0$ is an integer, and there exists a simple path from $u$ to $v$ in $G$ consisting of at least $k$ edges$\\}$. Show that the optimization problem LONGEST-PATH-LENGTH can be solved in polynomial time if and only if LONGEST-PATH $\\in$ P."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* LONGEST-PATH-LENGTH can be solved in polynomial time $\\Rightarrow$ LONGEST-PATH $\\in$ P\n",
    "\n",
    "Suppose it takes $O(n^k)$ time to determine that LONGEST-PATH-LENGTH is $k^*$. For any $k \\le k^*$, LONGEST-PATH$(\\langle G, u, v, k \\rangle)=1$, otherwise LONGEST-PATH$(\\langle G, u, v, k \\rangle)=0$, which takes $O(n^k)$ time."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* LONGEST-PATH-LENGTH can be solved in polynomial time $\\Leftarrow$ LONGEST-PATH $\\in$ P \n",
    "\n",
    "Suppose LONGEST-PATH can be solved in $O(n^k)$ time. Enumerate $k \\in [0, |V| - 1]$ to find the largest $k$ that LONGEST-PATH$(\\langle G, u, v, k \\rangle)=1$ takes $O(|V| \\cdot n^k) = O(n^c \\cdot n^k) = O(n^{ck})$ time, which is still polynomial, while the largest $k$ is the LONGEST-PATH-LENGTH."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 34.1-2\n",
    "\n",
    "> Give a formal definition for the problem of finding the longest simple cycle in an undirected graph. Give a related decision problem. Give the language corresponding to the decision problem."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Formal definition\n",
    "\n",
    "Instance: a graph $G$\n",
    "\n",
    "Solutions: a seqeunce of vertices in the graph\n",
    "\n",
    "Problem: find the simple cycle in $G$ which has the largest length $k$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Decision problem\n",
    "\n",
    "If $i = \\langle G, k \\rangle$ is an instance of the decision problem CYCLE, then CYCLE$(i)=1$ if there exists a simple cycle whose length is at least $k$, and CYCLE$(i)=0$ otherwise."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Language\n",
    "\n",
    "$$\n",
    "\\begin{array}{rl}\n",
    "\\text{CYCLE} = \\{ \\langle G, k \\rangle: & G = (V, E) \\text{ is an undirected graph}, \\\\\n",
    "                           & k \\ge 0 \\text{ is an integer, and} \\\\\n",
    "                           & \\text{there exists a simple cycle in } G \\text{ consisting of at least } k \\text{ edges } \\}.\n",
    "\\end{array}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 34.1-3\n",
    "\n",
    "> Give a formal encoding of directed graphs as binary strings using an adjacency-matrix representation. Do the same using an adjacency-list representation. Argue that the two representations are polynomially related."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Adjacency-matrix\n",
    "\n",
    "Suppose the matrix is $A$, then $A[u, v] = 1$ for any two vertices $u, v \\in G = (V, E)$ there exists a path between them, otherwise $A[u, v] = 0$. The encoding is the concatenation of the binary encoded $|V|$ and all the values in the matrix."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Adjacency-list\n",
    "\n",
    "The head of the encoding is $|V|$, then for each $u$, encode $u$ and its out-degree $|u|$, then followed the $|u|$ $v$s that has a path between them."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Polynomially related\n",
    "\n",
    "matrix -> list: get column number\n",
    "list -> matrix: fill 1s"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 34.1-4\n",
    "\n",
    "> Is the dynamic-programming algorithm for the 0-1 knapsack problem that is asked for in Exercise 16.2-2 a polynomial-time algorithm? Explain your answer."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "No. The algorithm runs in $O(nW)$ time. The concise encoding of $W$ has length $m = \\lfloor \\lg k \\rfloor + 1$, therefore the algorithm is worse than $O(k) = O(2^m)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 34.1-5\n",
    "\n",
    "> Show that if an algorithm makes at most a constant number of calls to polynomial-time subroutines and performs an additional amount of work that also takes polynomial time, then it runs in polynomial time. Also show that a polynomial number of calls to polynomial-time subrountines may result in an exponential-time algorithm."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Constant number\n",
    "\n",
    "$O \\left ( (((n^{d_1})^{d_2})\\dots)^{d_m} + n^{c} \\right ) = O \\left ( n^{d_1+d_2+\\dots+d_m} + n^{c} \\right )$ which is still polynomial time."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Polynomial number\n",
    "\n",
    "Suppose the size of the output of a subrountines is twice the size of the input, then the algorithm is at least $O(2^m)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 34.1-6\n",
    "\n",
    "> Show that the class P, viewed as a set of languages, is closed under union, intersection, concatenation, complement, and Kleene star. That is, if $L_1, L_2 \\in \\text{P}$, then $L_1 \\cup L_2 \\in \\text{P}$, $L_1 \\cap L_2 \\in \\text{P}$, $L_1L_2 \\in \\text{P}$, $\\overline{L_1} \\in \\text{P}$, and $L_1^* \\in \\text{P}$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Suppose $A_1$ accepts $L_1$ and $A_2$ accepts $L_2$, we can construct algorithm $A_3$ that runs under polynomial time:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* $L_1 \\cup L_2 \\in \\text{P}$\n",
    "\n",
    "```\n",
    "IF A_1(x) == 1 || A_2(x) == 1\n",
    "THEN RETURN 1\n",
    "ELSE RETURN 0\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* $L_1 \\cap L_2 \\in \\text{P}$\n",
    "\n",
    "```\n",
    "IF A_1(x) == 1 && A_2(x) == 1\n",
    "THEN RETURN 1\n",
    "ELSE RETURN 0\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* $L_1L_2 \\in \\text{P}$\n",
    "\n",
    "```\n",
    "FOR i = 1 .. n\n",
    "    IF A_1(x_1 ... x_i) == 1 && A_2(x_i+1 ... x_n) == 1\n",
    "    THEN RETURN 1\n",
    "RETURN 0\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* $\\overline{L_1} \\in \\text{P}$\n",
    "\n",
    "```\n",
    "IF A_1(x) == 1:\n",
    "RETURN 0\n",
    "RETURN 1\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* $L_1^* \\in \\text{P}$\n",
    "\n",
    "```\n",
    "IF x == epsilon\n",
    "THEN RETURN 1\n",
    "\n",
    "FOR i = 1 .. n\n",
    "    DP[i] = 0\n",
    "DP[0] = 1\n",
    "FOR i = 0 .. n\n",
    "    FOR j = i + 1 .. n\n",
    "        IF A_1(x_i ... x_j) == 1\n",
    "        THEN DP[j] = 1\n",
    "RETURN DP[n]\n",
    "```"
   ]
  }
 ],
 "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
}