Algo HW12

gistfile1.md

{ "metadata": { "name": "", "signature": "sha256:75263d9b9365b063bbd829aea610fabf3bcb740fe2c3f193680bfd648da74bd2" }, "nbformat": 3, "nbformat_minor": 0, "worksheets": [ { "cells": [ { "cell_type": "heading", "level": 3, "metadata": {}, "source": [ "1." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "####TSP $\in$ NP\n", "Given a graph $G$, a length $L$, and a candidate solution $A$ by guessing. The correctness can be checked by counting each vertex in $G$ occurs exactly once in $A$, and comparing $L$ to sum of all length of edges in $A$. Hence $A$ can be checked in polynomial time.\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "####HC $\propto$ TSP\n", "Given a graph $G$ be an input of HC. We can construct a complete graph $G'$ by letting $c(u,v) = 1$ for $G'.E$ if $(u,v) \in G.E$, and $c(u,v) = |G.V|+1$ for $G'.E$ if $(u,v) \notin G.E$. Thus, the answer is yes for HC with input $G$ $\iff$ the answer is yes for TSP with input graph $G'$ and upper bound $|G.V|$. Since the construction of $G'$ takes polynomial time, we conclude that HC $\propto$ TSP." ] }, { "cell_type": "heading", "level": 3, "metadata": {}, "source": [ "2." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "####CLIQUE $\in$ NP\n", "Given a graph $G$, and a candidate solution $A$ which contains $k$ vertices. To check the correctness, we can choose points from $A$ pairwisely and return answer yes if it forms an edge in $G.E$ for each pair. Otherwise, our algorithm returns no. Since we takes $O(|G.V|^2)$ checks, that implies $A$ can be checked in polynomial time." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "####3-CNF-SAT $\propto$ CLIQUE\n", "Given a 3-CNF Boolean expression $B = C_1 \land C_2 \land ... \land C_n$. We can construct a graph G as follows. Let $C_i = (l_1^i \lor l_2^i \lor l_3^i)$ be the $i$-th clause and its literals. We define vertices $v_1^i, v_2^i, v_3^i$ for $l_1^i \lor l_2^i \lor l_3^i$, respectively. Then we set edge $(v_h^i, v_k^j)$ if $v_h^i, v_k^j$ satisfying the following two conditions:\n", "- Their literals $l_h^i$ and $l_k^j$ are in different clauses, ie. $i \neq j$.\n", "- Their literals $l_h^i$ and $l_k^j$ are not the negation of each other.\n", "\n", "Note the construction of $G$ takes polynomial time. To complete the proof, we need to prove that CLIQUE answers yes using input $G$ adn integer $n$ $\iff$ 3-CNF-SAT answers yes using input $B$.\n", "\n", "Firstly, suppose 3-CNF-SAT answers yes, then there exists at least one literal $l_h^i$ is true for each clause $C_i$. We can choose one $l_h^i$ from each $C_i$ and collect it's corresponding vertices $G'.V = \{v_h^i\}$. Then $G'$ is a subgraph of $G$ and $|G'.V| = n$. For $v_h^i, v_k^j \in G'.V$, by our construction of $G'$, $v_h^i$ and $v_k^j$ must come from different clauses, furthermore, they are not the negation to each other by our hypothesis. $\implies$ $(v_h^i, v_k^j) \in G'.E$. Since $v_h^i, v_k^j$ are chosen arbitrarily, we conclude that CLIQUE answers yes using input $G$ and integer $n$.\n", "\n", "Conversely, suppose CLIQUE answers yes using input $G$ and integer $n$. Given a such subgraph $G'$. We may observe that if $u, v \in G'$, then it's corresponding literals $l_u, l_v$ must come from different clauses by our construction of $G$. Therefore, it derives that, for these $n$ vertices $v_1, ... , v_n \in G'.V$, it's corresponding literals $l_1, ... , l_n$ belong to $C_1, ... , C_n$ under some $1$-to-$1$ relation. Also, by our construction of $G$ again, $l_i$ and $l_j$ are not the negation of each other if $i \neq j$. That implies $C_i$ is true for all $i = 1, ... , n$ if we assign $l_1 = ... = l_n = $ true. $\implies$ 3-CNF-SAT answers yes using input $B$ and this completes the proof." ] } ], "metadata": {} } ] }