Chapter_34_NP-Completeness/exercises_34.4.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 34.4 NP-completeness proofs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 34.4-1\n",
    "\n",
    "> Consider the straightforward (nonpolynomial-time) reduction in the proof of Theorem 34.9. Describe a circuit of size $n$ that, when converted to a formula by this method, yields a formula whose size is exponential in $n$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Construct the circuit as follows: one input $x_1$ followed by a NOT gate, then followed AND gates which each connects all the outputs of previous steps.\n",
    "\n",
    "We can encode the circuit in $O(n^k)$, but the formula yielded grows exponentially in each step."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 34.4-2\n",
    "\n",
    "> Show the 3-CNF formula that results when we use the method of Theorem 34.10 on the formula (34.3)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "\\begin{array}{lll}\n",
    "\\phi' = y_1 &\\wedge& (y_1 \\leftrightarrow (y_2 \\wedge \\neg x_2)) \\\\\n",
    "         &\\wedge& (y_2 \\leftrightarrow (y_3 \\vee y_4)) \\\\\n",
    "         &\\wedge& (y_3 \\leftrightarrow (x_1 \\rightarrow x_2)) \\\\\n",
    "         &\\wedge& (y_4 \\leftrightarrow \\neg y_5) \\\\\n",
    "         &\\wedge& (y_5 \\leftrightarrow (y_6 \\vee x_4)) \\\\\n",
    "         &\\wedge& (y_6 \\leftrightarrow (\\neg x_1 \\leftrightarrow x_3)) \\\\\n",
    "\\end{array}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "\\begin{array}{lll}\n",
    "\\phi'' = y_1\n",
    "&\\wedge& (\\neg y1 \\vee \\neg y2 \\vee \\neg x2) \\\\\n",
    "&\\wedge& (\\neg y1 \\vee y2 \\vee \\neg x2) \\\\\n",
    "&\\wedge& (\\neg y1 \\vee y2 \\vee x2) \\\\\n",
    "&\\wedge& (y1 \\vee \\neg y2 \\vee x2) \\\\\n",
    "&\\wedge& (\\neg y2 \\vee y3 \\vee y4) \\\\\n",
    "&\\wedge& (y2 \\vee \\neg y3 \\vee \\neg y4) \\\\\n",
    "&\\wedge& (y2 \\vee \\neg y3 \\vee y4) \\\\\n",
    "&\\wedge& (y2 \\vee y3 \\vee \\neg y4) \\\\\n",
    "&\\wedge& (\\neg y3 \\vee \\neg x1 \\vee x2) \\\\\n",
    "&\\wedge& (y3 \\vee \\neg x1 \\vee \\neg x2) \\\\\n",
    "&\\wedge& (y3 \\vee x1 \\vee \\neg x2) \\\\\n",
    "&\\wedge& (y3 \\vee x1 \\vee x2) \\\\\n",
    "&\\wedge& (\\neg y4 \\vee \\neg y5) \\\\\n",
    "&\\wedge& (y4 \\vee y5) \\\\\n",
    "&\\wedge& (\\neg y5 \\vee y6 \\vee x4) \\\\\n",
    "&\\wedge& (y5 \\vee \\neg y6 \\vee \\neg x4) \\\\\n",
    "&\\wedge& (y5 \\vee \\neg y6 \\vee x4) \\\\\n",
    "&\\wedge& (y5 \\vee y6 \\vee \\neg x4) \\\\\n",
    "&\\wedge& (\\neg y6 \\vee \\neg x1 \\vee \\neg x3) \\\\\n",
    "&\\wedge& (\\neg y6 \\vee x1 \\vee x3) \\\\\n",
    "&\\wedge& (y6 \\vee \\neg x1 \\vee x3) \\\\\n",
    "&\\wedge& (y6 \\vee x1 \\vee \\neg x3) \\\\\n",
    "\\end{array}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "\\begin{array}{lll}\n",
    "\\phi'''\n",
    "&  =  & (y1 \\vee p \\vee q) \\\\\n",
    "&\\wedge& (y1 \\vee p \\vee \\neg q) \\\\\n",
    "&\\wedge& (y1 \\vee \\neg p \\vee q) \\\\\n",
    "&\\wedge& (y1 \\vee \\neg p \\vee \\neg q) \\\\\n",
    "&\\wedge& (\\neg y1 \\vee \\neg y2 \\vee \\neg x2) \\\\\n",
    "&\\wedge& (\\neg y1 \\vee y2 \\vee \\neg x2) \\\\\n",
    "&\\wedge& (\\neg y1 \\vee y2 \\vee x2) \\\\\n",
    "&\\wedge& (y1 \\vee \\neg y2 \\vee x2) \\\\\n",
    "&\\wedge& (\\neg y2 \\vee y3 \\vee y4) \\\\\n",
    "&\\wedge& (y2 \\vee \\neg y3 \\vee \\neg y4) \\\\\n",
    "&\\wedge& (y2 \\vee \\neg y3 \\vee y4) \\\\\n",
    "&\\wedge& (y2 \\vee y3 \\vee \\neg y4) \\\\\n",
    "&\\wedge& (\\neg y3 \\vee \\neg x1 \\vee x2) \\\\\n",
    "&\\wedge& (y3 \\vee \\neg x1 \\vee \\neg x2) \\\\\n",
    "&\\wedge& (y3 \\vee x1 \\vee \\neg x2) \\\\\n",
    "&\\wedge& (y3 \\vee x1 \\vee x2) \\\\\n",
    "&\\wedge& (\\neg y4 \\vee \\neg y5 \\vee p) \\\\\n",
    "&\\wedge& (\\neg y4 \\vee \\neg y5 \\vee \\neg p) \\\\\n",
    "&\\wedge& (y4 \\vee y5 \\vee p) \\\\\n",
    "&\\wedge& (y4 \\vee y5 \\vee \\neg p) \\\\\n",
    "&\\wedge& (\\neg y5 \\vee y6 \\vee x4) \\\\\n",
    "&\\wedge& (y5 \\vee \\neg y6 \\vee \\neg x4) \\\\\n",
    "&\\wedge& (y5 \\vee \\neg y6 \\vee x4) \\\\\n",
    "&\\wedge& (y5 \\vee y6 \\vee \\neg x4) \\\\\n",
    "&\\wedge& (\\neg y6 \\vee \\neg x1 \\vee \\neg x3) \\\\\n",
    "&\\wedge& (\\neg y6 \\vee x1 \\vee x3) \\\\\n",
    "&\\wedge& (y6 \\vee \\neg x1 \\vee x3) \\\\\n",
    "&\\wedge& (y6 \\vee x1 \\vee \\neg x3) \\\\\n",
    "\\end{array}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 34.4-3\n",
    "\n",
    "> Professor Jagger proposes to show that SAT $\\le_\\text{P}$ 3-CNF-SAT by using only the truth-table technique in the proof of Theorem 34.10, and not the other steps. That is, the professor proposes to take the boolean formula $\\phi$, form a truth table for its variables, derive from the truth table a formula in 3-DNF that is equivalent to $\\neg \\phi$, and then negate and apply DeMorgan's laws to produce a 3-CNF formula equivalent to $\\phi$. Show that this strategy does not yield a polynomial-time reduction."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Suppose the number of variables in the formula is $n$, the number of rows in the truth table is $2^n$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 34.4-4\n",
    "\n",
    "> Show that the problem of determining whether a boolean formula is a tautology is complete for co-NP. (Hint: See Exercise 34.3-7.)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Suppose the language of determining whether a boolean formula is a tautology is $L$ and the boolean formula is denoted by $\\phi$. Then $\\overline{L}$ is equivalent to 3-CNF-SAT with formula $\\neg \\phi$, therefore $\\overline{L}$ is complete for NP. Based on Exercise 34.3-7, $L$ is complete for co-NP."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 34.4-5\n",
    "\n",
    "> Show that the problem of determining the satisfiability of boolean formulas in disjunctive normal form is polynomial-time solvable."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The formula in disjunctive normal form evaluates to 1 if any of the clauses in it could be evaluated to 1. A cluase could be evaluated to 1 if there isn't a literal $x$ that both $x$ and $\\neg x$ appeared in the clause. Thus suppose there are $n$ clauses and the maximum number of literals in one clause is $m$, the time complexity is $O(nm^2)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 34.4-6\n",
    "\n",
    "> Suppose that someone gives you a polynomial-time algorithm to decide formula satisfiability. Describe how to use this algorithm to find satisfying assignments in polynomial time."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Suppose the algorithm is $A$, the formula is $\\phi$ and the variables are $(x_1, ..., x_n)$.\n",
    "\n",
    "If $A$ rejects $\\phi$, then there is no solution.\n",
    "\n",
    "Else if $A$ accepts $\\phi$, then for each $x_i$, replace $x_i$ by 0, if the transformed formula $\\phi'$ is accepted by $A$, then $x_i = 0$, otherwise $x_i = 1$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 34.4-7\n",
    "\n",
    "> Let 2-CNF-SAT be the set of satisfiable boolean formulas in CNF with exactly 2 literals per clause. Show that 2-CNF-SAT $\\in$ P. Make your algorithm as efficient as possible. (Hint: Observe that $x \\vee y$ is equivalent to $\\neg x \\rightarrow y$. Reduce 2-CNF-SAT to an efficiently solvable problem on a directed graph.)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[2SAT](http://www.math.ucsd.edu/~sbuss/CourseWeb/Math268_2007WS/2SAT.pdf)"
   ]
  }
 ],
 "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
}