Chapter_34_NP-Completeness/exercises_34.3.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 34.3 NP-completeness and reducibility"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 34.3-1\n",
    "\n",
    "> Verify that the circuit in Figure 34.8(b) is unsatisfiable."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "results = []\n",
    "for x1 in [0, 1]:\n",
    "    for x2 in [0, 1]:\n",
    "        for x3 in [0, 1]:\n",
    "            g11 = x1 | x2\n",
    "            g12 = ~~x3\n",
    "            g13 = x1 & x2 & ~x3\n",
    "            g21 = g11 & g12\n",
    "            g22 = g12 | g13\n",
    "            result = g21 & g22 & g13\n",
    "            results.append(result)\n",
    "print(max(results))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 34.3-2\n",
    "\n",
    "> Show that the $\\le_\\text{P}$ relation is a transitive relation on languages. That is, show that if $L_1 \\le_\\text{P} L_2$ and $L_2 \\le_\\text{P} L_3$, then $L_1 \\le_\\text{P} L_3$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Suppose the reduction function of $L_1 \\le_\\text{P} L_2$ is $f$ and the reduction function of $L_2 \\le_\\text{P} L_3$ is $g$, then the reduction function from $L_1$ to $L_3$ is $g(f)$. Suppose $f$ runs in $O(n^k)$ time with some constant $k$, then the size of output is also $O(n^k)$. Suppose $g$ runs in $O(n^c)$ time with some constant $c$, then the total time of $g(f)$ is $O((n^k)^c) = O(n^{kc})$, which is polynomial to $n$. Therefore $L_1$ is polynomial-time reducible to $L_3$, $L_1 \\le_\\text{P} L_3$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 34.3-3\n",
    "\n",
    "> Prove that $L \\le_{\\text{P}} \\overline{L}$ if and only if $\\overline{L} \\le_{\\text{P}} L$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* $L \\le_{\\text{P}} \\overline{L} \\Rightarrow \\overline{L} \\le_{\\text{P}} L$\n",
    "\n",
    "Suppose the polynomial-time reduction is $f$, then $\\forall x \\in L, f(x) \\in \\overline{L}$, and $\\forall x \\notin L, f(x) \\notin \\overline{L}$. $x \\notin L$ means $x \\in \\overline{L}$, $f(x) \\notin \\overline{L}$ means $f(x) \\in L$, therefore we can use the same $f$ for reduction.\n",
    "\n",
    "* $\\overline{L} \\le_{\\text{P}} L \\Rightarrow L \\le_{\\text{P}} \\overline{L}$\n",
    "\n",
    "Symmetric."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 34.3-4\n",
    "\n",
    "> Show that we could have used a satisfying assignment as a certificate in an alternative proof of Lemma 34.5. Which certificate makes for an easier proof?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Use only inputs and calculate the output."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 34.3-5\n",
    "\n",
    "> The proof of Lemma 34.6 assumes that the working storage for algorithm $A$ occupies a contiguous region of polynomial size. Where in the proof do we exploit this assumption? Argue that this assumption does not involve any loss of generality."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Just like virtual memory, we can add a mapping from scattered regions to one continguous region."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 34.3-6\n",
    "\n",
    "> A language $L$ is __*complete*__ for a language class $C$ with respect to polynomial-time reductions if $L \\in C$ and $L' \\le_\\text{P} L$ for all $L' \\in C$. Show that $\\emptyset$ and $\\{0, 1\\}^*$ are the only languages in $\\text{P}$ that are not complete for $\\text{P}$ with respect to polynomial-time reductions."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* $\\emptyset$: rejects everything.\n",
    "* $\\{0, 1\\}^*$: accepts everything.\n",
    "* others: we can choose a string in $L$ (in polynomial time since $L' \\in P$) if $i \\in L'$ is accepted, and a string in $\\overline{L}$ if it is rejected."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 34.3-7\n",
    "\n",
    "> Show that, with respect to polynomial-time reductions (see Exercise 34.3-6), $L$ is complete for $\\text{NP}$ if and only if $\\overline{L}$ is complete for $\\text{co-NP}$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* $L \\Rightarrow \\overline{L}$\n",
    "\n",
    "$L \\in \\text{NP}$ and $\\forall L' \\in \\text{NP}, L' \\le_\\text{P} L$\n",
    "\n",
    "$L \\in \\text{NP} \\Rightarrow \\overline{L} \\in \\text{co-NP}$\n",
    "\n",
    "$\\forall L' \\in \\text{NP}, L' \\le_\\text{P} L \\Rightarrow \\forall \\overline{L'} \\in \\text{NP}, \\overline{L'} \\le_\\text{P} L \\Rightarrow \\forall L' \\in \\text{co-NP}, \\overline{L'} \\le_\\text{P} L \\Rightarrow \\forall L' \\in \\text{co-NP}, L' \\le_\\text{P} \\overline{L}$\n",
    "\n",
    "* $\\overline{L} \\Rightarrow L$\n",
    "\n",
    "Symmetric"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 34.3-8\n",
    "\n",
    "> The reduction algorithm $F$ in the proof of Lemma 34.6 constructs the circuit $C = f(x)$ based on knowledge of $x$, $A$ and $k$. Professor Sartre observes that the string $x$ is input to $F$, but only the existence of $A$, $k$, and the constant factor implicit in the $O(n^k)$ running time is known to $F$ (since language $L$ belongs to $\\text{NP}$), not their actual values. Thus the professor concludes that $F$ can't possibly construct the circuit $C$ and that language CIRCUIT-SAT is not necessarily NP-hard. Explain the flaw in professor's reasoning."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Without a concrete $A(x, y)$ we can't prove $L \\in \\text{NP}$."
   ]
  }
 ],
 "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
}