CS计算机代考程序代写 \documentclass{article}

\documentclass{article}
\usepackage[utf8]{inputenc}

\title{CS301HW13}
\author{ }
\date{May 2021}

\begin{document}

\maketitle
\section*{Part One}

\section*{Answer the following questions regarding HITTING\textunderscore SET and VERTEX\textunderscore COVER as defined below.}
HITTING\textunderscore SET \(= { | S \) is a set, T is a set of subsets of S, and h is an integer where there is S’ \( ⊆ S with |S’| = h and S’ contains at least one element from each set in T} \)

VERTEX\textunderscore COVER = { | G = (V, E) is an undirected graph that contains a set of k nodes that touch all edges in G}

a. Find a hitting set S’ of size h=2 for the sets S = {a, b, c, d, e, f, g} and T = {{a,b,c}, {c,d,e}, {e,f,g}}.

b. Find a vertex cover of size 2 for the graph G = (V, E) where V = {a, b, c, d, e} and E = {{a,b}, {b,c}, {a,d}, {b,e}, {d,e}}.

c. Describe the certificate for a polynomial time verifier for VERTEX\textunderscore COVER.

d. Describe the certificate for a polynomial time verifier for HITTING\textunderscore SET.

e. Describe a polynomial time reduction from VERTEX\textunderscore COVER to HITTING\textunderscore SET.

\section*{2 Use the reductions described in the book to perform the following conversions.}
\section*{2a}
\Phi = ( a \vee b ) \wedge (a \vee \bar{b} \vee c \vee d)

\section*{2b}
\Phi = (a \vee b \vee b) \wedge (\bar{a} \vee \bar{b} \vee \bar{b})

\section*{2c}
\Phi = (a \vee b \vee b) \wedge (\bar{a} \vee \bar{b} \vee \bar{b})

\end{document}