### 数学代写|计算复杂度理论代写Computational complexity theory代考|NP-Completeness

statistics-lab™ 为您的留学生涯保驾护航 在代写计算复杂度理论Computational complexity theory方面已经树立了自己的口碑, 保证靠谱, 高质且原创的统计Statistics代写服务。我们的专家在代写计算复杂度理论Computational complexity theory代写方面经验极为丰富，各种代写计算复杂度理论Computational complexity theory相关的作业也就用不着说。

• Statistical Inference 统计推断
• Statistical Computing 统计计算
• (Generalized) Linear Models 广义线性模型
• Statistical Machine Learning 统计机器学习
• Longitudinal Data Analysis 纵向数据分析
• Foundations of Data Science 数据科学基础

## 数学代写|计算复杂度理论代写Computational complexity theory代考|Cook’s Theorem

The notion of reducibilities was first developed in recursion theory. In general, a reducibility $\leq_{r}$ is a binary relation on languages that satisfies the reflexivity and transitivity properties and, hence, it defines a partial ordering on the class of all languages. In this section, we introduce the notion of polynomial-time many-one reducibility. Let $A \subseteq \Sigma^{}$ and $B \subseteq \Gamma^{}$ be two languages. We say that $A$ is many-one reducible to $B$, denoted by $A \leq_{m} B$, if there exists a computable function $f: \Sigma^{} \rightarrow \Gamma^{}$ such that for each $x \in \Sigma^{*}, x \in A$ if and only if $f(x) \in B$. If the reduction function $f$ is further known to be computable in polynomial time, then we say that $A$ is polynomial-time many-one reducible to $B$ and write $A \leq_{m}^{P} B$. It is easy to see that polynomial-time many-one reducibility does satisfy the reflexivity and transitivity properties and, hence, indeed is a reducibility.
Proposition $2.8$ The following hold for all sets $A, B$, and $C$ :
(a) $A \leq_{m}^{P} A$
(b) $A \leq_{m}^{P} B, B \leq_{m}^{P} C \Rightarrow A \leq_{m}^{P} C$.
Note that if $A \leq_{m}^{P} B$ and $B \in P$, then $A \in P$. In general, we say a complexity class $\mathcal{C}$ is closed under the reducibility $\leq_{r}$ if $A \leq_{r} B$ and $B \in \mathcal{C}$ imply $A \in \mathcal{C}$

Proposition 2.9 The complexity classes $P, N P$, and PSPACE are all closed under $\leq_{m}^{P}$

Note that the complexity class $E X P=\bigcup_{c>0} D T I M E\left(2^{c n}\right)$ is not closed under $\leq_{m}^{P}$. People sometimes, therefore, study a weaker class of exponential-time computable sets EXPPOLY = $\bigcup_{k>0} D T I M E\left(2^{n^{k}}\right)$, which is closed under $\leq_{m}^{P}$.

For any complexity class $\mathcal{C}$ that is closed under a reducibility $\leq_{r}$, we say a set $B$ is $\leq_{r}$ hard for class $C$ if $A \leq_{r} B$ for all $A \in \mathcal{C}$ and we say a set $B$ is $\leq_{r}-$ complete for class $\mathcal{C}$ if $B \in \mathcal{C}$ and $B$ is $\leq_{r}$-hard for $\mathcal{C}$. For convenience, we say a set $B$ is $\mathcal{C}$-complete if $B$ is $\leq_{m}^{P}$-complete for the class $\mathcal{C}$. $^{2}$ Thus, a set $B$ is $N P$-complete if $B \in N P$ and $A \leq_{m}^{P} B$ for all $A \in N P$. An $N P$-complete set $B$ is a maximal element in $N P$ under the partial ordering $\leq_{m}^{P}$. Thus, it is not in $P$ if and only if $P \neq N P$.

## 数学代写|计算复杂度理论代写Computational complexity theory代考|More NP-Complete Problems

The importance of the notion of $N P$-completeness is witnessed by thousands of $N P$-complete problems from a variety of areas in computer science, discrete mathematics, and operations research. Theoretically, all these problems can be proved to be $N P$-complete by reducing SAT to them. It is practically much easier to prove new $N P$-complete problems from some other known $N P$-complete problems that have similar structures as the new problems. In this section, we study some best-known $N P$-complete problems that may be useful to obtain new $N P$-completeness results.
VERTEX COVER (VC): Given a graph $G=(V, E)$ and an integer $K \geq 0$, determine whether $G$ has a vertex cover of size at most $K$, that is, determine whether $V$ has a subset $V^{\prime}$ of size $\leq K$ such that each $e \in E$ has at least one end point in $V^{\prime}$.
Theorem 2.14 VC is NP-complete.
Proof. It is easy to see that $\mathrm{VC}$ is in $N P$. To show that $\mathrm{VC}$ is complete for $N P$, we reduce 3-SAT to it.

Let $F$ be a 3-CNF formula with $m$ clauses $C_{1}, C_{2}, \ldots, C_{m}$ over $n$ variables $x_{1}, x_{2}, \ldots, x_{n}$. We construct a graph $G_{F}$ of $2 n+3 m$ vertices as follows. The vertices are named $x_{i}, \bar{x}{i}$ for $1 \leq i \leq n$, and $c{j k}$ for $1 \leq j \leq m$, $1 \leq k \leq 3$. The vertices are connected by the following edges: for each $i, 1 \leq i \leq n$, there is an edge connecting $x_{i}$ and $\bar{x}{i}$; for each $j, 1 \leq j \leq m$, there are three edges connecting $c{j, 1}, c_{j, 2}, c_{j, 3}$ into a triangle and, in addition, if $C_{j}=\ell_{1}+\ell_{2}+\ell_{3}$, then there are three edges connecting each $c_{j, k}$ to the vertex named $\ell_{k}, 1 \leq k \leq 3$. Figure $2.1$ shows the graph $G_{F}$ for $F=\left(x_{1}+\bar{x}{2}+x{3}\right)\left(\bar{x}{1}+x{3}+\bar{x}{4}\right)\left(\bar{x}{2}+\bar{x}{3}+x{4}\right) .$

We claim that $F$ is satisfiable if and only if $G_{F}$ has a vertex cover of size $n+2 m$. First, suppose that $F$ is satisfiable by a truth assignment $\tau$. Let $S_{1}=\left{x_{i}: \tau\left(x_{i}\right)=1,1 \leq i \leq n\right} \cup\left{\bar{x}{i}: \tau\left(x{i}\right)=0,1 \leq i \leq n\right}$. Next for each $j, 1 \leq j \leq m$, let $c_{j, j}$ be the vertex of the least index $j_{k}$ such that $c_{j, j_{k}}$ is adjacent to a vertex in $S_{1}$. (By the assumption that $\tau$ satisfies $F$, such an index $j_{k}$ always exists.) Then, let $S_{2}=\left{c_{j, r}: 1 \leq r \leq 3, r \neq j_{k}, 1 \leq j \leq\right.$ $m}$ and $S=S_{1} \cup S_{2}$. It is clear that $S$ is a vertex cover for $G_{F}$ of size $n+2 m$

Conversely, suppose that $G_{F}$ has a vertex cover $S$ of size at most $n+$ $2 m$. As each triangle over $c_{j_{1}}, c_{j_{2}}, c_{j_{3}}$ must have at least two vertices in $S$ and each edge $\left{x_{i}, \bar{x}{i}\right}$ has at least one vertex in $S, S$ is of size exactly $n+2 m$ with exactly two vertices from each triangle $c{j_{1}}, c_{j_{2}}, c_{j_{3}}$ and exactly one vertex from each edge $\left{x_{i}, \bar{x}{i}\right}$. Define $\tau\left(x{i}\right)=1$ if $x_{i} \in S$ and $\tau\left(x_{i}\right)=0$ if $\bar{x}{i} \in S$. Then, each clause $C{j}$ must have a true literal which is the one adjacent to the vertex $c_{j, k}$ that is not in $S$. Thus, $F$ is satisfied by $\tau$.

The above construction is clearly polynomial-time computable. Hence, we have proved 3-SAT $\leq_{m}^{P} V$ VC.

## 数学代写|计算复杂度理论代写Computational complexity theory代考|Polynomial-Time Turing Reducibility

Polynomial-time many-one reducibility is a strong type of reducibility on decision problems (i.e., languages) that preserves the membership in the class $P$. In this section, we extend this notion to a weaker type of reducibility called polynomial-time Turing reducibility that also preserves the membership in $P$. Moreover, this weak reducibility can also be applied to search problems (i.e., functions).

Intuitively, a problem $A$ is Turing reducible to a problem $B$, denoted by $A \leq_{T} B$, if there is an algorithm $M$ for $A$ which can ask, during its computation, some membership questions about set $B$. If the total amount of time used by $M$ on an input $x$, excluding the querying time, is bounded by $p(|x|)$ for some polynomial $p$, and furthermore, if the length of each query asked by $M$ on input $x$ is also bounded by $p(|x|)$, then we say $A$ is polynomial-time Turing reducible to $B$ and denote it by $A \leq_{T}^{P} B$. Let us look at some examples.

Example $2.20$ (a) For any set $A, \bar{A} \leq_{T}^{P} A$, where $\bar{A}$ is the complement of $A$. This is achieved easily by asking the oracle $A$ whether the input $x$ is in $A$ or not and then reversing the answer. Note that if $N P \neq \operatorname{coNP}$, then $\overline{\mathrm{SAT}}$ is not polynomial-time many-one reducible to SAT. So, this demonstrates that the $\leq_{T}^{P}$-reducibility is potentially weaker than the $\leq_{m}^{P}$-reducibility (cf. Exercise $2.14$ ).
(b) Recall the $N P$-complete problem CLIQUE. We define a variation of the problem CLIQUE as follows:
EXACT-CLIQUE: Given a graph $G=(V, E)$ and an integer $K \geq$ 0 , determine whether it is true that the maximum-size clique of $G$ is of size $K$.
It is not clear whether EXACT-CLIQUE is in $N P$. We can guess a subset $V^{\prime}$ of $V$ of size $K$ and verify in polynomial time that the subgraph of $G$ induced by $V^{\prime}$ is a clique. However, there does not seem to be a nondeterministic algorithm that can check that there is no clique of size greater than $K$ in polynomial time. Therefore, this problem may seem even harder

than the $N P$-complete problem CLIQUE. In the following, however, we show that this problem is actually polynomial-time equivalent to CLIQUE in the sense that they are polynomial-time Turing reducible to each other. Thus, either they are both in $P$ or they are both not in $P$.

First, let us describe an algorithm for the problem CLIQUE that can ask queries to the problem EXACT-CLIQUE. Assume that $G=(V, E)$ is a graph and $K$ is a given integer. We want to know whether there is a clique in $G$ that is of size $K$. We ask whether $(G, k)$ is in EXACT-CLIQUE for each $k=1,2, \ldots,|V|$. Then, we will get the maximum size $k^{}$ of the cliques of $G$. We answer YES to the original problem CLIQUE if and only if $K \leq k^{}$.

Conversely, let $G=(V, E)$ be a graph and $K$ a given integer. Note that the maximum clique size of $G$ is $K$ if and only if $(G, K) \in$ CLIQUE and $(G, K+1) \notin$ CLIQUE. Thus, the question of whether $(G, K) \in$ ExACTCLIQUE can be solved by asking two queries to the problem CLIQUE. (See Exercise 3.3(b) for more studies on EXACT-CLIQUE.)

## 数学代写|计算复杂度理论代写Computational complexity theory代考|Cook’s Theorem

(二)一个≤米磷乙,乙≤米磷C⇒一个≤米磷C.

## 数学代写|计算复杂度理论代写Computational complexity theory代考|More NP-Complete Problems

VERTEX COVER (VC)：给定一个图G=(在,和)和一个整数ķ≥0, 判断是否G最多有一个 size 的顶点覆盖ķ，即判断是否在有一个子集在′大小的≤ķ使得每个和∈和至少有一个端点在在′.

## 数学代写|计算复杂度理论代写Computational complexity theory代考|Polynomial-Time Turing Reducibility

(b) 回顾ñ磷-完成问题CLIQUE。我们将问题 CLIQUE 的一个变体定义如下：
EXACT-CLIQUE：给定一个图G=(在,和)和一个整数ķ≥0 , 判断最大大小的团是否为真G是大小ķ.

## 有限元方法代写

tatistics-lab作为专业的留学生服务机构，多年来已为美国、英国、加拿大、澳洲等留学热门地的学生提供专业的学术服务，包括但不限于Essay代写，Assignment代写，Dissertation代写，Report代写，小组作业代写，Proposal代写，Paper代写，Presentation代写，计算机作业代写，论文修改和润色，网课代做，exam代考等等。写作范围涵盖高中，本科，研究生等海外留学全阶段，辐射金融，经济学，会计学，审计学，管理学等全球99%专业科目。写作团队既有专业英语母语作者，也有海外名校硕博留学生，每位写作老师都拥有过硬的语言能力，专业的学科背景和学术写作经验。我们承诺100%原创，100%专业，100%准时，100%满意。

## MATLAB代写

MATLAB 是一种用于技术计算的高性能语言。它将计算、可视化和编程集成在一个易于使用的环境中，其中问题和解决方案以熟悉的数学符号表示。典型用途包括：数学和计算算法开发建模、仿真和原型制作数据分析、探索和可视化科学和工程图形应用程序开发，包括图形用户界面构建MATLAB 是一个交互式系统，其基本数据元素是一个不需要维度的数组。这使您可以解决许多技术计算问题，尤其是那些具有矩阵和向量公式的问题，而只需用 C 或 Fortran 等标量非交互式语言编写程序所需的时间的一小部分。MATLAB 名称代表矩阵实验室。MATLAB 最初的编写目的是提供对由 LINPACK 和 EISPACK 项目开发的矩阵软件的轻松访问，这两个项目共同代表了矩阵计算软件的最新技术。MATLAB 经过多年的发展，得到了许多用户的投入。在大学环境中，它是数学、工程和科学入门和高级课程的标准教学工具。在工业领域，MATLAB 是高效研究、开发和分析的首选工具。MATLAB 具有一系列称为工具箱的特定于应用程序的解决方案。对于大多数 MATLAB 用户来说非常重要，工具箱允许您学习应用专业技术。工具箱是 MATLAB 函数（M 文件）的综合集合，可扩展 MATLAB 环境以解决特定类别的问题。可用工具箱的领域包括信号处理、控制系统、神经网络、模糊逻辑、小波、仿真等。