\documentclass[12pt]{article} \usepackage{tikz} \usetikzlibrary{automata,positioning,arrows} \newcommand{\lf}{\left\lfloor} \newcommand{\rf}{\right\rfloor} \newcommand{\lc}{\left\lceil} \newcommand{\rc}{\right\rceil} \newcommand{\Ceil}[1]{\left\lceil {#1}\right\rceil} \newcommand{\ceil}[1]{\left\lceil {#1}\right\rceil} \newcommand{\floor}[1]{\left\lfloor{#1}\right\rfloor} \newcommand{\N}{{\sf N}} \newcommand{\goes}{\rightarrow} \newcommand{\st}{\mathrel{:}} \newcommand{\nth}{n^{th}} \newcommand{\es}{\emptyset} \begin{document} \newif{\ifshowsoln} \showsolntrue % comment out to NOT show solution inside \ifshowsoln and \fi blocks. \centerline{\bf Homework 8 Morally DUE April 28 at 11:00 AM} \begin{enumerate} \item (35 points) Let $$IS_\alpha = \{ G \st G \hbox{ has an Independent Set of size } \ge \alpha n \}$$ where $n$ is the number of vertices in $G$. \begin{enumerate} \item (15 points) Show that $IS_{1/3}$ is NP-complete. (Hint: look at the proof that $IS$ is NP-complete.) \item (20 points) Show that $$IS_{1/2} \le IS_{7/8}$$ You can assume that the graph $G$ you are originally given has $n$ vertices where $n$ is divisible by 8. (You must give the reduction; you can't just say they are both NP-complete, though they are.) \end{enumerate} \item (30 points) In class we did the proof that $3SAT\le IS$. Let $\phi$ be $$(x_1 \vee \neg x_2 \vee x_3) \wedge (\neg x_1 \vee x_2 \vee x_4) \wedge (x_1\vee \neg x_3 \vee \neg x_4) \wedge (\neg x_1 \vee x_2 \vee x_3)$$ Apply the reduction to obtain a graph $G$ and a number $k$ such that $\phi$ is satisfable IFF $G$ has an ind set of size $k$. Give the graph BOTH as a drawing and FORMALLY in terms of listing its vertices and edges. \item (35 points) A Sam-TM is one that allows the instruction $$\delta(q,a)=(p,b,L)$$ which means that, if the machine is in state $q$ and is looking at $a$, then the state changes to $p$, The $a$ is overwritten with a $b$, AND the head then moves left. Write the part of the formula that models this transition in the proof of the Cook-Levin Theorem. \end{enumerate} \end{document}