Homework15.tex

\section{0521}\label{sec:0521}
\begin{questions}
    \question 已知顶点覆盖问题是NP完全的，那么如果所有顶点的度数都是偶数，
    能不能设计出多项式时间的确定性算法？

    \begin{solution}
        \textbf{
            \color{red}
            虽然我们不能证明$\mathcal{P} \ne \mathcal{NP}$，
            但是这里我们还是认为NP完全问题不存在多项式时间的算法可以解决。
        }

        在一个任意的图中，考察所有顶点的度数和。
        因为每条边贡献的总度数为$2$，所以所有顶点的度数和为偶数。
        所以图中度数为奇数的顶点一定有偶数个。

        在该图中添加一个新的三角形，$p$为该三角形的一个顶点，
        顶点$p$与图中所有奇数度的顶点$v_i$之间连一条边。
        因为有偶数个奇数度的顶点，所以生成的图$G'$中所有顶点的度数均为偶数。

        为了覆盖新添加的三角形，该三角形中一定有且只有两个顶点存在于$G'$的最小覆盖中。
        因为顶点$p$的度数一定大于三角形中另外两个顶点，
        所以选中顶点$p$一定不会比不选中顶点p的情况覆盖的边少。
        因此这两个顶点中一定包含顶点p。

        因此从$G'$的顶点覆盖中移除这两个点，就是$G$的顶点覆盖。

        因此求参数为$(G,k)$的顶点覆盖问题可以多项式归约到求参数为$(G',k+2)$的顶点覆盖问题。
        因为前者是NP完全的，所以后者也是NP完全的。

    \end{solution}


    \question 证明3-MAX-SAT问题是NP完全问题。

    3-MAX-SAT问题是指对于给定的由$m$个子句构成的合取范式$F$，每个子句恰好有$3$个文字，
    如何对布尔变量$x_1,x_2, \dots ,x_n$赋值，使得$F$中满足的子句尽可能多。

    \begin{solution}

        \textbf{
            \color{red}
            首先给出问题的判定问题形式，然后证明它是NP问题，再归约。
        }


        \begin{parts}
            \part {
                3-MAX-SAT问题的判定问题形式是$F$中能否有$k$个子句满足。
            }
            \part {
                对于任意一组$x_1,x_2, \dots ,x_n$的值，可以通过逐个计算$m$个子句的值并对满足的子句计数，判断是否有$k$个子句满足。
                时间复杂度为$O(m)$。
            }
            \part {
                假设存在一个算法$\mathcal{A}(F,k)$可以解决3-MAX-SAT问题的判定问题形式，
                \begin{itemize}
                    \item 应用该算法求解$\{x_i\}_n \gets \mathcal{A}(F, m)$
                    \item 则$\{x_i\}_n$能使$F$中所有子句同时为真
                \end{itemize}
                因此3SAT问题可以多项式归约到3-MAX-SAT问题。
            }
        \end{parts}

        % 3-SAT问题是3-MAX-SAT问题的特例，即$k=m$，由于3-SAT问题是NP完全的，所以3-MAX-SAT问题也是NP完全的。

    \end{solution}

\end{questions}