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

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代考|Algebraic Criterion

In this section, we provide some tools to prove the elusiveness of a Boolean function. We begin with a simple one.

Theorem 5.10 A Boolean function with an odd number of truth assignments is elusive.

Proof. The constant functions $f \equiv 0$ and $f \equiv 1$ have 0 and $2^{n}$ truth assignments, respectively. Hence, a Boolean function with an odd number of truth assignments must be a nonconstant function. If $f$ has at least two variables and $x_{i}$ is one of them, then the number of truth assignments of $f$ is the sum of those of $\left.f\right|{x{i}=0}$ and $\left.f\right|{x{i}=1}$. Therefore, either $\left.f\right|{x{i}=0}$ or $\left.f\right|{x{i}=1}$ has an odd number of truth assignments and is not a constant function. Thus, for any decision tree computing $f$, tracing the subtrees with an odd number of truth assignments, we will meet all variables in a path from the root to a leaf.
Define
$$p_{f}(k)=\sum_{t \in{0,1}^{n}} f(t) k^{| t t},$$
where $|t|$ is the number of l’s in string $t$ (recall that a Boolean assignment may be viewed as a binary string). It is easy to see that $p_{f}(1)$ is the number of truth assignments for $f$. The following theorem is an extension of Theorem $5.10$.

Theorem 5.11 For a Boolean function $f$ of $n$ variables, $(k+1)^{n-D(f)} \mid p_{f}(k)$.
Proof. We prove this theorem by induction on $D(f)$. First, we note that if $f \equiv 0$, then $p_{f}(k)=0$ and if $f \equiv 1$ then $p_{f}(k)=(k+1)^{n}$ (by the binomial theorem). This means that the theorem holds for $D(f)=0$. Now, consider $f$ with $D(f)>0$ and a decision tree $T$ of depth $D(f)$ computing $f$. Without loss of generality, assume that the root of $T$ is labeled by $x_{1}$. Denote $f_{0}=\left.f\right|{x{1}=0}$ and $f_{1}=\left.f\right|{x{1}=1}$. Then
\begin{aligned} p_{f}(k) &=\sum_{t \in{0,1}^{n}} f(t) k^{|t|} \ &=\sum_{s \in{0,1}^{n-1}} f(0 s) k^{|s|}+\sum_{s \in{0,1}^{n-1}} f(1 s) k^{1+|s|} \ &=p_{f_{0}}(k)+k p_{f_{1}}(k) . \end{aligned}
Note that $D\left(f_{0}\right) \leq D(f)-1$ and $D\left(f_{1}\right) \leq D(f)-1$. By the induction hypothesis, $(k+1)^{n-1-D\left(f_{0}\right)} \mid p_{f_{0}}(k)$ and $(k+1)^{n-1-D\left(f_{1}\right)} \mid p_{f_{1}}(k)$. Thus, $(k+1)^{n-D(f)} \mid p_{f}(k)$
An important corollary is as follows. Denote $\mu(f)=p_{f}(-1)$.

## 数学代写|计算复杂度理论代写Computational complexity theory代考|Monotone Graph Properties

In this section, we prove a general lower bound for the decision tree complexity of nontrivial monotone graph properties.

First, let us analyze how to use Theorem $5.13$ to study nontrivial monotone graph properties. Note that every graph property is weakly symmetric and for any nontrivial monotone graph property, the complete graph must have the property and the empty graph must not have the property. Therefore, if we want to use Theorem $5.13$ to prove the elusiveness of a nontrivial monotone graph property, we need to verify only one condition that the number of variables is a prime power. For a graph property, however, the number of variables is the number of possible edges, which equals $n(n-1) / 2$ for $n$ vertices and it is not a prime power for $n>3$. Thus, Theorem $5.13$ cannot be used directly to show elusiveness of graph properties. However, it can be used to establish a little weaker results by finding a partial assignment such that the number of remaining variables becomes a prime power. The following lemmas are derived from this idea.

Lemma $5.16$ If $\mathcal{P}$ is a nontrivial monotone property of graphs of order $n=2^{m}$, then $D(\mathcal{P}) \geq n^{2} / 4$.

Proof. Let $H_{i}$ be the disjoint union of $2^{m-i}$ copies of the complete graph of order $2^{i}$. Then $H_{0} \subset H_{1} \subset \cdots \subset H_{m}=K_{n}$. Since $\mathcal{P}$ is nontrivial and is monotone, $H_{m}$ has the property $\mathcal{P}$ and $H_{0}$ does not have the property $\mathcal{P}$. Thus, there exists an index $j$ such that $H_{j+1}$ has the property $\mathcal{P}$ and $H_{j}$ does not have the property $\mathcal{P}$. Partition $H_{j}$ into two parts with vertex sets $A$ and $B$, respectively, each containing exactly $2^{m-j-1}$ disjoint copies of the complete graph of order $2^{j}$. Let $K_{A, B}$ be the complete bipartite graph between $A$ and $B$. Then $H_{j+1}$ is a subgraph of $H_{j} \cup K_{A, B}$. So, $H_{j} \cup K_{A, B}$ has the property $\mathcal{P}$. Now, let $f$ be the function on bipartite graphs between $A$ and $B$ such that $f$ has the value 1 at a bipartite graph $G$ between $A$ and $B$ if and only if $H_{j} \cup G$ has the property $\mathcal{P}$. Then $f$ is a nontrivial monotone weakly symmetric function with $|A| \cdot|B|\left(=2^{2 m-2}\right)$ variables. By Theorem $5.13, D(\mathcal{P}) \geq D(f)=2^{2 m-2}=n^{2} / 4$.

## 数学代写|计算复杂度理论代写Computational complexity theory代考|Topological Criterion

In this section, we introduce a powerful tool to study the elusiveness of monotone Boolean functions. We start with some concepts in topology.
A triangle is a two-dimensional polygon with the minimum number of vertices. A tetrahedron is a three-dimensional polytope with the minimum number of vertices. They are the simplest polytopes with respect to the specific dimensions. They are both called simplexes. The concept of simplexes is a generalization of the notions of triangles and tetrahedrons. In general, a simplex is a polytope with the minimum number of vertices among all polytopes with certain dimension. For example, a point is a zero-dimensional simplex and a straight line segment is a one-dimensional simplex. The convex hull of linearly independent $n+1$ points in a Euclidean space is an $n$-dimensional simplex.

A face of a simplex $S$ is a simplex whose vertex set is a subset of vertices of $S$. A geometric simplicial complex is a family $\Gamma$ of simplexes satisfying the following conditions:
(a) For $S \in \Gamma$, every face of $S$ is in $\Gamma$.
(b) For $S, S^{\prime} \in \Gamma, S \cap S^{\prime}$ is a face for both $S$ and $S^{\prime}$.
(c) For $S, S^{\prime} \in \Gamma, S \cap S^{\prime}$ is also a simplex in $\Gamma$.
In Figure $5.5$, there are three examples; first two are not geometric simplicial complexes, the last one is.

Consider a set $X$ and a family $\Delta$ of subsets of $X . \Delta$ is called an (abstract) simplicial complex if for any $A$ in $\Delta$ every subset of $A$ also belongs to $\Delta$. Each member of $\Delta$ is called a face of $\Delta$. The dimension of a face $A$ is $|A|-1$. Any face of dimension 0 is called a vertex. For example, consider a set $X={a, b, c, d}$. The following family is a simplicial complex on $X$ :
\begin{aligned} \Delta=&{\emptyset,{a},{b},{c},{d},{a, b},{b, c},\ &{c, d},{d, a},{a, c},{a, b, c},{a, c, d}} \end{aligned}
The set ${a, b, c}$ is a face of dimension 2 and the empty set $\emptyset$ is a face of dimension $-1$.

## 数学代写|计算复杂度理论代写Computational complexity theory代考|Algebraic Criterion

pF(ķ)=∑吨∈0,1nF(吨)ķ|吨吨,

## 数学代写|计算复杂度理论代写Computational complexity theory代考|Topological Criterion

(a) 对于小号∈Γ, 每一张脸小号在Γ.
(b) 为小号,小号′∈Γ,小号∩小号′是一张脸小号和小号′.
(c) 为小号,小号′∈Γ,小号∩小号′也是一个单纯形Γ.

\begin{aligned} \Delta=&{\emptyset,{a},{b},{c},{d},{a, b},{b, c},\ &{c, d},{ d, a},{a, c},{a, b, c},{a, c, d}} \end{对齐}\begin{aligned} \Delta=&{\emptyset,{a},{b},{c},{d},{a, b},{b, c},\ &{c, d},{ d, a},{a, c},{a, b, c},{a, c, d}} \end{对齐}

## 有限元方法代写

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 环境以解决特定类别的问题。可用工具箱的领域包括信号处理、控制系统、神经网络、模糊逻辑、小波、仿真等。

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

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代考|Random Oracles

Consider the class $\mathcal{C}$ of all subsets of ${0,1}^{*}$ and define subclasses $\mathcal{A}=\left{A \in \mathcal{C}: P^{A}=N P^{A}\right}$ and $B=\left{B \in \mathcal{C}: P^{B} \neq N P^{B}\right}$. One of the approaches to study the relativized $P=$ ? $N P$ question is to compare the two subclasses $\mathcal{A}$ and $\mathcal{B}$ to see which one is larger. In this subsection, we give a brief introduction to this study based on the probability theory on the space $\mathcal{C}$.

To define the notion of probability on the space $\mathcal{C}$, it is most convenient to identify each element $X \in \mathcal{C}$ with its characteristic sequence $\alpha_{X}=\chi_{X}(\lambda) \chi_{X}(0) \chi_{X}(1) \chi_{X}(00) \ldots$ (i.e., the $k$ th bit of $\alpha_{X}$ is 1 if and only if the $k$ th string of ${0,1}^{*}$, under the lexicographic ordering, is in $\left.X\right)$ and treat $\mathcal{C}$ as the set of all infinite binary sequences or, equivalently, the Cartesian product ${0,1}^{\infty}$. We can define a topology on $\mathcal{C}$ by letting the set ${0,1}$ have the discrete topology and forming the product topology on $\mathcal{C}$. This is the well-known Cantor space. We now define the uniform probability measure $\mu$ on $\mathcal{C}$ as the product measure of the simple equiprobable measure on ${0,1}$, that is, $\mu{0}=\mu{1}=1 / 2$. In other words, for any integer $n \geq 1$, the $n$th bit of a random sequence $\alpha \in \mathcal{C}$ has the equal probability to be 0 or 1 . If we identify each real number in $[0,1]$ with its binary expansion, then this measure $\mu$ is the Lebesgue measure on $[0,1] . .^{5}$

For any $u \in{0,1}^{}$, let $\Gamma_{u}$ be the set of all infinite binary sequences that begin with $u$, that is, $\Gamma_{u}^{u}=\left{u \beta: \beta \in{0,1}^{\infty}\right}$. Each set $\Gamma_{u}$ is called a cylinder. All cylinders $\Gamma_{u}, u \in{0,1}^{}$, together form a basis of open neighborhoods of the space $\mathcal{C}$ (under the product topology). It is clear that $\mu\left(\Gamma_{u}\right)=2^{-|u|}$ for all $u \in{0,1}^{}$. The smallest $\sigma$-field containing all $\Gamma_{u}$, for all $u \in{0,1}^{}$, is called the Borel field. ${ }^{6}$ Each set in the Borel field, called a Borel set, is measurable.

The question of which of the two subclasses $\mathcal{A}$ and $B$ is larger can be formulated, in this setting, as to whether $\mu(\mathcal{A})$ is greater than $\mu(\mathcal{B})$. In the following, we show that $\mu(\mathcal{A})=0$.

An important idea behind the proof is Kolmogorov’s zero-one law of tail events, which implies that if an oracle class is insensitive to a finite number of bit changes, then its probability is either zero or one. This property holds for the classes $\mathcal{A}$ and $B$ as well as most other interesting oracle classes.

## 数学代写|计算复杂度理论代写Computational complexity theory代考|Structure of Relativized NP

Although the meaning of relativized collapsing and relativized separation results is still not clear, many relativized results have been proven. These results show a variety of possible relations between the well-known complexity classes. In this section, we demonstrate some of these relativized results on complexity classes within $N P$ to show what the possible relations are between $P, N P, N P \cap \operatorname{co} N P$, and $U P$. The relativized results on the classes beyond the class $N P$, that is, those on $N P, P H$, and $P S P A C E$, will be discussed in later chapters.

The proofs of the following results are all done by the stageconstruction diagonalization. The proofs sometimes need to satisfy simultaneously two or more potentially conflicting requirements that make the proofs more involved.
Theorem 4.20 (a) $(\exists A) P^{A} \neq N P^{A} \cap \operatorname{coN} P^{A} \neq N P^{A}$.
(b) $(\exists B) P^{B} \neq N P^{B}=\cos P^{B}$.
(c) $(\exists C) P^{C}=N P^{C} \cap \operatorname{coN} P^{C} \neq N P^{C}$.
Proof. (a): This can be done by a standard diagonalization proof. We leave it as an exercise (Exercise 4.16(a)).
(b): Let $\left{M_{i}\right}$ be an effective enumeration of all polynomial-time oracle DTMs and $\left{N_{i}\right}$ an effective enumeration of all polynomial-time oracle NTMs. For any set $B$, let $K_{B}=\left{\left\langle i, x, 0^{j}\right\rangle: N_{i}^{B}\right.$ accepts $x$ in $j$ moves $}$. Then, by the relativized proof of Theorem $2.11, K_{B}$ is $\leq_{m}^{P}$-complete for the class $N P^{B}$. Let $L_{B}=\left{0^{n}:(\exists x)|x|=n, x \in B\right}$. Then, it is clear that $L_{B} \in N P^{B}$. We are going to construct a set $B$ to satisfy the following requirements:
$R_{0, t}$ : for each $x$ of length $t, x \notin K_{B} \Longleftrightarrow(\exists y,|y|=t) x y \in B$, $R_{1, i}:(\exists n) 0^{n} \in L_{B} \Longleftrightarrow M_{i}^{A}$ does not accept $0^{n} .$
Note that if requirements $R_{0, t}$ are satisfied for all $t \geq 1$, then $\overline{K_{B}} \in N P^{B}$ and, hence, $N P^{B}=\operatorname{coN} N P^{B}$, and if requirements $R_{1, i}$ are satisfied for all $i \geq 1$, then $L_{B} \notin P^{B}$ and, hence, $P^{B} \neq N P^{B}$.

We construct set $B$ by a stage construction. At each stage $n$, we will construct finite sets $B_{n}$ and $B_{n}^{\prime}$ such that $B_{n-1} \subseteq B_{n}, B_{n-1}^{\prime} \subseteq B_{n}^{\prime}$, and $B_{n} \cap$ $B_{n}^{\prime}=\emptyset$ for all $n \geq 1$. Set $B$ is define as the union of all $B_{n}, n \geq 0$.

The requirement $R_{0, t}, t \geq 1$, is to be satisfied by direct diagonalization at stage $2 t$. The requirements $R_{1, i}, i \geq 1$, are to be satisfied by a delayed diagonalization in the odd stages. We always try to satisfy the requirement $R_{1, i}$ with the least $i$ such that $R_{1, i}$ is not yet satisfied. We cancel an integer $i$ when $R_{1, i}$ is satisfied. Before stage 1 , we assume that $B_{0}=B_{0}^{\prime}=\emptyset$ and that none of integers $i$ is cancelled.

## 数学代写|计算复杂度理论代写Computational complexity theory代考|Graphs and Decision Trees

We first review the notion of graphs and the Boolean function representations of graphs. ${ }^{1}$ A graph is an ordered pair of disjoint sets $(V, E)$ such that $E$ is a set of pairs of elements in $V$ and $V \neq \emptyset$. The elements in the set $V$ are called vertices and the elements in the set $E$ are called edges. Two vertices are adjacent if there is an edge between them. Two graphs are isomorphic if there exists a one-to-one correspondence between their vertex sets that preserves adjacency.

A path is an alternating sequence of distinct vertices and edges starting and ending with vertices such that every vertex is an end point of its neighboring edges. The length of a path is the number of edges appearing in the path. A graph is connected if every pair of vertices are joined by a path.

Let $V={1, \ldots, n}$ be the vertex set of a graph $G=(V, E)$. Then its adjacency matrix $\left[x_{i j}\right]$ is defined by
$$x_{i j}= \begin{cases}1 & \text { if }{i, j} \in E, \ 0 & \text { otherwise. }\end{cases}$$
Note that $x_{i j}=x_{j i}$ and $x_{i i}=0$. So, the graph $G$ can be determined by $n(n-$ 1)/ 2 independent variables $x_{i j}, 1 \leq i<j \leq n$. For any property $\mathcal{P}$ of graphs with $n$ vertices, we define a Boolean function $f_{p}$ over $n(n-1) / 2$ variables $x_{i j}, 1 \leq i<j \leq n$, as follows:
$$f_{p}\left(x_{12}, \ldots, x_{n-1, n}\right)= \begin{cases}1 & \begin{array}{l} \text { if the graph } G \text { represented by }\left[x_{i, j}\right] \text { has } \ \text { the property } \mathcal{P} \end{array} \ 0 & \text { otherwise. }\end{cases}$$
Then $\mathcal{P}$ can be determined by $f_{p}$. For example, the property of connectivity corresponds to the Boolean functions $f_{\text {con }}$ of $n(n-1) / 2$ variables such that $f_{c o n}\left(x_{12}, \ldots, x_{n-1, n}\right)=1$ if and only if the graph $G$ represented by $\left[x_{i j}\right]$ is connected.

Not every Boolean function of $n(n-1) / 2$ variables represents a graph property because a graph property should be invariant under graph isomorphism. A Boolean function $f$ of $n(n-1) / 2$ variables is called a graph property if for every permutation $\sigma$ on the vertex set ${1, \ldots, n}$,
$$f\left(x_{12}, \ldots, x_{n-1, n}\right)=f\left(x_{\sigma(1) \sigma(2)}, \ldots, x_{\sigma(n-1) \sigma(n)}\right) \text {. }$$

## 数学代写|计算复杂度理论代写Computational complexity theory代考|Structure of Relativized NP

(二)(∃乙)磷乙≠ñ磷乙=因⁡磷乙.
（C）(∃C)磷C=ñ磷C∩和⁡磷C≠ñ磷C.

(b): 让\left{M_{i}\right}\left{M_{i}\right}是所有多项式时间预言机 DTM 的有效枚举，并且\left{N_{i}\right}\left{N_{i}\right}所有多项式时间预言机 NTM 的有效枚举。对于任何集合乙， 让K_{B}=\left{\left\langle i, x, 0^{j}\right\rangle: N_{i}^{B}\right.$接受$x$在$j$移动$}K_{B}=\left{\left\langle i, x, 0^{j}\right\rangle: N_{i}^{B}\right.$接受$x$在$j$移动$}. 然后，由定理的相对化证明2.11,ķ乙是≤米磷- 完成课程ñ磷乙. 让L_{B}=\left{0^{n}:(\exists x)|x|=n, x \in B\right}L_{B}=\left{0^{n}:(\exists x)|x|=n, x \in B\right}. 那么，很明显大号乙∈ñ磷乙. 我们将构建一个集合乙满足以下要求：
R0,吨: 对于每个X长度吨,X∉ķ乙⟺(∃是,|是|=吨)X是∈乙, R1,一世:(∃n)0n∈大号乙⟺米一世一个不接受0n.

## 数学代写|计算复杂度理论代写Computational complexity theory代考|Graphs and Decision Trees

X一世j={1 如果 一世,j∈和, 0 否则。

Fp(X12,…,Xn−1,n)={1 如果图表 G 代表为 [X一世,j] 有   财产 磷 0 否则。

F(X12,…,Xn−1,n)=F(Xσ(1)σ(2),…,Xσ(n−1)σ(n)).

## 有限元方法代写

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 环境以解决特定类别的问题。可用工具箱的领域包括信号处理、控制系统、神经网络、模糊逻辑、小波、仿真等。

## 数学代写|计算复杂度理论代写Computational complexity theory代考|CATS 2013

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代考|Unrelativizable Proof Techniques

First, a common view is that the question of whether $P$ is equal to $N P$ is a difficult question in view of Theorem 4.14. As most proof techniques developed in recursion theory, including the basic diagonalization and simulation techniques, relativize, any attack to the $P=$ ? NP question must use a new, unrelativizable proof technique. Many more contradictory relativized results like Theorem $4.14$ (including some in Section 4.8) on the relations between complexity classes tend to support this viewpoint. On the other hand, some unrelativizable proof techniques do exist in complexity theory. For instance, we will apply an algebraic technique to collapse the complexity class PSPACE to a subclass $I P$ (see Chapter 10). As there exists an oracle $X$ that separates $P S P A C E^{X}$ from $I P^{X}$, this proof is indeed unrelativizable. Though this is a breakthrough in the theory of relativization, it seems still too early to tell whether such techniques are applicable to a wider class of questions.

## 数学代写|计算复杂度理论代写Computational complexity theory代考|Independence Results

One of the most interesting topics in set theory is the study of independence results. A statement $A$ is said to be independent of a theory $T$ if there exist two models $M_{1}$ and $M_{2}$ of $T$ such that $A$ is true in $M_{1}$ and false in $M_{2}$. If a statement $A$ is known to be independent of the theory $T$, then neither $A$ nor its negation $\neg A$ is provable in theory $T$. The phenomenon of contradictory relativized results looks like a mini-independent result: neither the statement $P=N P$ nor its negation $P \neq N P$ is provable by relativizable techniques. This observation raises the question of whether they are provable within a formal proof system. In the following, we present a simple argument showing that this is indeed possible.

To prepare for this result, we first briefly review the concept of a formal proof system. An axiomatizable theory is a triple $F=(\Sigma, W, T)$, where $\Sigma$ is a finite alphabet, $W \subseteq \Sigma^{*}$ is a recursive set of well-formed formulas, and $T \subseteq W$ is an r.e. set. The elements in $T$ are called theorems. If $T$ is recursive, we say the theory $F$ is decidable. We are only interested in a sound theory in which we can prove the basic properties of TMs. In other words, we assume that TMs form a submodel for $F$, all basic properties of TMs are provable in $F$, and all theorems in $F$ are true in the TM model. In the following, we let $\left{M_{i}\right}$ be a fixed enumeration of multi-tape DTMs.
Theorem 4.15 For any formal axiomatizable theory $F$ for which $T M s$ form a submodel, we can effectively find a DTM $M_{i}$ such that $L\left(M_{i}\right)=\emptyset$ and neither ” $P P^{L\left(M_{i}\right)}=N P^{L\left(M_{i}\right) “}$ nor ” $P^{L\left(M_{i}\right)} \neq N P^{L\left(M_{i}\right) “}$ is provable in $F$.

Proof. Let $A$ and $B$ be two recursive sets such that $P^{A}=N P^{A}$ and $P^{B} \neq$ $N P^{B}$. Define a TM $M$ such that $M$ accepts $(j, x)$ if and only if among the first $x$ proofs in $F$ there is a proof for the statement ” $P^{L\left(M_{j}\right)}=N P^{L\left(M_{j}\right)}$ ” and $x \in B$ or there is a proof for the statement ” $P^{L\left(M_{j}\right)} \neq N P^{L\left(M_{j}\right)}$ ” and $x \in A$. By the recursion theorem, there exists an index $j_{0}$ such that $M_{j_{0}}$ accepts $x$ if and only if $M$ accepts $\left(j_{0}, x\right)$. (See, e.g., Rogers (1967) for the recursion theorem.)

Now, if there is a proof for the statement ” $P^{L\left(M_{k b}\right)}=N P^{L\left(M_{k}\right)}$ ” in $F$, then for almost all $x, M$ accepts $\left(j_{0}, x\right)$ if and only if $x \in B$. That is, the set $L\left(M_{j_{0}}\right)$ differs from the set $B$ by only a finite set and, hence, $P^{B} \neq N P^{B}$ implies $P^{L\left(M_{f 0}\right)} \neq N P^{L\left(M_{j 0}\right)}$. Similarly, if there exists a proof for the statement ” $P^{L\left(M_{j 0}\right)} \neq N P^{L\left(M_{f 0}\right)}$ “, then $L\left(M_{j_{0}}\right)$ differs from $A$ by only a finite set theory $F$, we conclude that neither ” $P^{L\left(M_{f 0}\right)}=N P^{L\left(M_{j 0}\right) “}$ nor ” $P^{L\left(M_{f 0}\right)} \neq$ $N P^{L\left(M_{f 0}\right)}$, , is provable in $F$.

Furthermore, because neither ” $P^{L\left(M_{f 0}\right)}=N P^{L\left(M_{f 0}\right)}$ ” nor ” $P^{L\left(M_{f 0}\right)} \neq$ $N P^{L\left(M_{j_{0}}\right) \text { ” }}$ is provable in $F$, the machine $M_{j_{0}}$ does not accept any input $x$, that is, $L\left(M_{j_{0}}\right)=\emptyset$.

## 数学代写|计算复杂度理论代写Computational complexity theory代考|Positive Relativization

Still another viewpoint is that the formulation of the relativized complexity class $N P^{A}$ used in Theorem $4.14$ does not reflect correctly the concept of nondeterministic computation. Consider the set $L_{B}$ in the proof of Theorem 4.14. Note that although each computation path of the oracle NTM $M$ that accepts $L_{B}$ asks only one question to determine whether $0^{n}$ is in $B$, the whole computation tree of $M^{B}(x)$ makes an exponential number of queries. While it is recognized that this is the distinctive property of an NTM to make, in the whole computation tree, an exponential number of moves, the fact that $M$ can access an exponential amount of information about the oracle $B$ immediately makes the oracle NTMs much stronger than oracle DTMs. To make the relation between oracle NTMs and oracle DTMs close to that between regular NTMs and regular DTMs, we must not allow the oracle NTMs to make arbitrary queries. Instead, we would like to know whether an oracle NTM that is allowed to make, in the whole computation tree, only a polynomial number of queries is stronger than an oracle DTM. When we add these constraints to the oracle NTMs, it turns out that the relativized $P=$ ?NP question is equivalent to the unrelativized version. This result supports the viewpoint that the relativized separation of Theorem $4.14$ is due to the extra information that an oracle NTM can access, rather than the nondeterminism of the NTM and, hence, this kind of separation results bear no relation to the original unrelativized questions. This type of relativization is called positive relativization. We present a simple result of this type in the following.

## 有限元方法代写

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 环境以解决特定类别的问题。可用工具箱的领域包括信号处理、控制系统、神经网络、模糊逻辑、小波、仿真等。

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

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代考|Incomplete Problems in NP

We have seen many $N P$-complete problems in Chapter 2. Many natural problems in $N P$ turn out to be $N P$-complete. There are, however, a few interesting problems in $N P$ that are not likely to be solvable in deterministic polynomial time but also are not known to be $N P$-complete. The study of these problems is thus particularly interesting, because it not only can classify the inherent complexity of the problems themselves but can also provide a glimpse of the internal structure of the class $N P$. We start with some examples.

Example 4.1 GRAPH ISOMORPHISM (GIso): Given two graphs $G_{1}=$ $\left(V_{1}, E_{1}\right)$ and $G_{2}=\left(V_{2}, E_{2}\right)$, determine whether they are isomorphic, that is, whether there is a bijection $f: V_{1} \rightarrow V_{2}$ such that ${u, v} \in E_{1}$ if and only if ${f(u), f(v)} \in E_{2}$.

The problem SuBGRAPH IsomORPHISM, which asks whether a given graph $G_{1}$ is isomorphic to a subgraph of another given graph $G_{2}$, can be proved to be $N P$-complete easily. However, the problem GIso is neither known to be $N P$-complete nor known to be in $P$, despite extensive studies in recent years. We will prove in Chapter 10, through the notion of interactive proof systems, that GIso is not $N P$-complete unless the polynomial-time hierarchy collapses to the level $\Sigma_{2}^{P}$. This result suggests that GIso is probably not $N P$-complete.

There are many number-theoretic problems in $N P$ that are neither known to be $N P$-complete nor known to be in $P$. We list three of them that have major applications in cryptography. An integer $x \in \mathbb{Z}{n}^{}$ is called a quadratic residue modulo $n$ if $x \equiv y^{2} \bmod n$ for some $y \in \mathbb{Z}{n}^{}$. We write $x \in Q R_{n}$ to denote this fact.

## 数学代写|计算复杂度理论代写Computational complexity theory代考|One-Way Functions and Cryptography

One-way functions are a fundamental concept in cryptography, having a number of important applications, including public-key cryptosystems,pseudorandom generators, and digital signatures. Intuitively, a one-way function is a function that is easy to compute but its inverse is hard to compute. Thus it can be applied to develop cryptosystems that need easy encoding but difficult decoding. If we identify the intuitive notion of “easiness” with the mathematical notion of “polynomial-time computability,” then one-way functions are subproblems of $N P$, because the inverse function of a polynomial-time computable function is computable in polynomial-time relative to an oracle in $N P$, assuming that the functions are polynomially honest. Indeed, all problems in $N P$ may be viewed as one-way functions.

Example 4.5 Define a function $f_{\mathrm{SAT}}$ as follows: For each Boolean function $F$ over variables $x_{1}, \ldots, x_{n}$ and each Boolean assignment $\tau$ on $x_{1}, \ldots, x_{n}$
$$f_{\mathrm{SAT}}(F, \tau)= \begin{cases}\langle F, 1\rangle & \text { if } \tau \text { satisfies } F, \ \langle F, 0\rangle & \text { otherwise. }\end{cases}$$
It is easily seen that $f_{\text {SAT }}$ is computable in polynomial time. Its inverse mapping $\langle F, 1\rangle$ to $\langle F, \tau\rangle$ is exactly the search problem of finding a truth assignment for a given Boolean formula. Using the notion of polynomialtime Turing reducibility and the techniques developed in Chapter 2, we can see that the inverse function of $f_{\mathrm{SAT}}$ is polynomial-time equivalent to the decision problem SAT. Thus, the inverse of $f_{\mathrm{SAT}}$ is not polynomial-time computable if $P \neq N P$.

Strictly speaking, function $f_{\mathrm{SAT}}$ is, however, not really a one-way function because it is not a one-to-one function and its inverse is really a multivalued function. In the following, we define one-way functions for one-to-one functions. We say that a function $f: \Sigma^{} \rightarrow \Sigma^{}$ is polynomially honest if there is a polynomial function $q$ such that for each $x \in \Sigma^{*}$, $|f(x)| \leq q(|x|)$ and $|x| \leq q(|f(x)|)$.

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

The concept of relativization originates from recursive function theory. Consider, for example, the halting problem. We may formulate it in the following form: $K=\left{x \mid M_{x}(x)\right.$ halts $}$, where $M_{x}$ is the $x$ th TM in a standard enumeration of all TMs. Now, if we consider all oracle TMs, we may ask whether the set $K_{A}=\left{x \mid M_{x}^{A}(x)\right.$ halts $}$ is recursive relative to $A$. This is the halting problem relative to set $A$. It is easily seen from the original proof for the nonrecursiveness of $K$ that $K_{A}$ is nonrecursive relative to $A$ (i.e., no oracle TM can decide $K_{A}$ using $A$ as an oracle). Indeed, most results in recursive function theory can be extended to hold relative to any oracle set. We say that such results relativize. In this section, we investigate the problem of whether $P=N P$ in the relativized form. First, we need to define what is meant by relativizing the question of whether $P=N P$. For any set $A$, recall that $P^{A}(\circ r P(A))$ is the class of sets computable in polynomial time by oracle DTMs using $A$ as the oracle and, similarly, NPA (or $N P(A))$ is the class of sets accepted in polynomial time by oracle NTMs classes $P$ and $N P$, we show that the relativized $P=? N P$ question has both the positive and negative answers, depending on the oracle set $A$.
Theorem $4.14$ (a) There exists a recursive set $A$ such that $P^{A}=N P^{A}$.
(b) There exists a recursive set $B$ such that $P^{B} \neq N P^{B}$.
Proof. (a): Let $A$ be any set that is $\leq_{m}^{P}$-complete for PSPACE. Then, by Savitch’s theorem, we have
$$N P^{A} \subseteq N P S P A C E=P S P A C E \subseteq P^{A} .$$

## 数学代写|计算复杂度理论代写Computational complexity theory代考|Incomplete Problems in NP

SubGRAPH IsomORPHISM 的问题，它询问给定的图是否G1与另一个给定图的子图同构G2, 可以证明是ñ磷- 轻松完成。然而，问题 GIso 不为人所知ñ磷-完成也不知道在磷，尽管近年来进行了广泛的研究。我们将在第 10 章通过交互式证明系统的概念证明 GIso 不是ñ磷-完成，除非多项式时间层次结构崩溃到该级别Σ2磷. 该结果表明 GIso 可能不是ñ磷-完全的。

## 数学代写|计算复杂度理论代写Computational complexity theory代考|One-Way Functions and Cryptography

F小号一个吨(F,τ)={⟨F,1⟩ 如果 τ 满足 F, ⟨F,0⟩ 否则。

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

(b) 存在一个递归集乙这样磷乙≠ñ磷乙.

ñ磷一个⊆ñ磷小号磷一个C和=磷小号磷一个C和⊆磷一个.

## 有限元方法代写

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 环境以解决特定类别的问题。可用工具箱的领域包括信号处理、控制系统、神经网络、模糊逻辑、小波、仿真等。

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

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代考|Alternating Turing Machines

The polynomial-time hierarchy was formally defined by oracle TMs. As the oracles play a mysterious role in the computation of an oracle TM, it is relatively more difficult to analyze the computation of such machines. The characterization of Theorem $3.8$ provides a different view, and it has been found useful for many applications. In this section, we formalize this characterization as a computational model, called the alternating Turing machine (abbreviated as ATM), that can be used to define the complexity classes in the polynomial-time hierarchy without using the notion of oracles.

An ATM $M$ is an ordinary NTM with its states partitioned into two subsets, called the universal states and the existential states. An ATM operates exactly the same as an NTM, but the notion of its acceptance of an input is defined differently. Thus, the computation of an ATM $M$ is a computation tree of configurations with each pair $(\alpha, \beta)$ of parent and child configurations satisfying $\alpha \vdash_{M} \beta$. We say a configuration is a universal configuration if it is in a universal state, and it is an existential configuration if it is in an existential state.

To define the notion of an ATM accepting an input, we assign, inductively, the label ACCEPT to some of the nodes in this computation tree as follows: A leaf is labeled ACCEPT if and only if it is in the accepting state. An internal node in the universal state is labeled with ACCEPT if and only if all of its children are labeled with ACCEPT. An internal node in the existential state is labeled with ACCEPT if and only if at least one of its children is labeled with ACCEPT. We say an ATM M accepts an input $x$ if the root of the computation tree is labeled with ACCEPT using the above labeling system. Thus an NTM is just an ATM in which all states are classified as existential states.

When an NTM $M$ accepts an input $x$, an accepting computation path is a witness to this fact. Also, we define time $_{M}(x)$ to be the length of a shortest accepting path. For an ATM $M$, to demonstrate that it accepts an input $x$, we need to display the accepting computation subtree $T_{a c c}$ of the computation tree $T$ of $M(x)$ that has the following properties:
(i) The root of $T$ is in $T_{a c c}$.
(ii) If $u$ is an internal existential node in $T_{a c c}$, then exactly one child of $u$ in $T$ is in $T_{a c c}$.

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

Our first PSPACE-complete problem is the space-bounded halting problem (SBHP).
SPACE Bounded Halting Problem (SBHP): Given a DTM $M$, an input $x$, and an integer $s$, written in the unary form $0^{s}$, determine whether $M$ accepts $x$ within space bound $s$.
Theorem 3.23 SBHP is $\leq_{m}^{P}$-complete for PSPACE.
Proof. The proof is similar to that of Theorem 2.11.
The existence of a PSPACE-complete set implies that if the polynomial-time hierarchy is properly infinite, then PSPACE properly contains $P H$.

Theorem 3.24 If $P H=P S P A C E$, then the polynomial-time hierarchy collapses to $\Sigma_{k}^{P}$ for some $k>0$.

Proof. If $P H=P S P A C E$, then SBHP $\in P H=\bigcup_{k \geq 0} \Sigma_{k}^{P}$ and, hence, SBHP $\in \Sigma_{k}^{P}$ for some $k \geq 0$. This implies that PSPACE $\subseteq \Sigma_{k}^{P}$, because $\Sigma_{k}^{P}$ is closed under the $\leq_{m}^{P}$-reducibility.

The first natural PSPACE-complete problem is a generalization of $S A T_{k}$. The inputs to this problem are Boolean formulas with quantifiers $(\exists x)$ and $(\forall x)$. An occurrence of a variable $v$ in a Boolean formula $F$ is a bounded variable if there is a quantifier $(\exists v)$ or $(\forall v)$ in $F$ such that this occurrence of $v$ is in the scope of the quantifier. A Boolean formula $F$ is called a quantified Boolean formula if every occurrence of every variable in $F$ is a bounded variable. For instance, $F=(\forall x)[(\forall y)[(\exists z)[x \bar{y} z+\bar{x} y \bar{z}] \rightarrow(\exists z)[(x \bar{z}+\bar{x} z)(y \bar{z}+\bar{y} z)]]]$ is a quantified Boolean formula. In the above, we used brackets […] to denote the scope of a quantifier and $\rightarrow$ to denote the Boolean operation $(a \rightarrow b)=(\bar{a}+b)$. Each quantified Boolean formula has a normal form in which all quantifiers occur before any occurrence of a Boolean variable, and the scope of each quantifier is the rest of the formula to its right. For instance, the normal form (with renaming) of the above formula $F$ is $(\forall x)(\forall y)(\forall z)(\exists w)[(x \bar{y} z+\bar{x} y \bar{z}) \rightarrow((x \bar{w}+\bar{x} w)(y \bar{w}+\bar{y} w))]$
QUANTIFIED BOOLEAN FORMULA (QBF): Given a quantified Boolean formula $F$, determine whether $F$ is true.

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

All complete problems studied so far are candidates for intractable problems, but their intractability still depends on the separation of the classes $N P, P S P A C E$, and $P H$ from the class $P$. Are there natural problems that are provably intractable in the sense that they can be proved not belonging to $P$ ? In this section, we present a few problems that are complete for $E X P$ and, hence, not in $P$.

Our first $E X P$-complete problem is the bounded halting problem on deterministic machines with the time bound encoded in binary form.
EXPONENTIAL-Time BoUnDEd HALTING PROBLEM (EXP-BHP): Given a DTM $M$, a string $x$, and an integer $n>0$, written in the binary form, determine whether $M(x)$ halts in $n$ moves.
Proposition 3.30 EXP-BHP is EXP-complete.
Proof. If $L$ is accepted by a DTM $M$ in time $2^{c n}$, then the function $f(x)=$ $\left\langle M, x, 2^{c|x|}\right\rangle$ is a polynomial-time reduction from $L$ to ExP-BHP.

We note that in the above problem, if the time bound $n$ is written in the unary form (as in the problem BHP), then the problem becomes polynomial-time solvable. Indeed, there is a simple translation of most $P$-complete problems ${ }^{1}$ to $E X P$-complete problems by more succinct encodings of the inputs. In the following, we demonstrate this idea on the famous $P$-complete problem, CIRCUIT VALUE Problem (CVP).

Let $C$ be a Boolean circuit ${ }^{2}$ satisfying the following property: $C$ has $n$ gates numbered from 1 to $n$; we let $C(i)$ denote the gate of $C$ numbered $i$. There are four types of gates in circuit $C$ : ZERO gates, ONE gates, AND gates, and OR gates. A ZERO (ONE) gate has no input and one output whose value is 0 (1, respectively). An AND (OR) gate has two inputs and one output whose value is the Boolean product (Boolean sum, respectively) of the two inputs. If the gate $i$ is an AND or OR gate, then its two inputs are the outputs of two gates whose numbers are lower than $i$. Note that this circuit $C$ does not have input gates and so it computes a unique Boolean value (the output of gate $n$ ). If the circuit is given explicitly, then its output value is computable in polynomial time. (In fact, it is $P$-complete; see Theorem 6.41). In the following, we consider the encoding of the circuit by a DTM. We say that a DTM $M$ generates a circuit $C$ of size $n$ in time $m$ if for all $i, 0 \leq i \leq n, M(i)$ outputs a triple $\langle b, j, k\rangle$ in $m$ moves, with $0 \leq b \leq 3$ and $1 \leq j, k<i$ if $b \leq 1$, such that
(i) If $b=0$, then $C(i)=C(j) \cdot C(k)$;
(ii) If $b=1$, then $C(i)=C(j)+C(k)$;
(iii) If $b=2$, then $C(i)=0$;
(iv) If $b=3$, then $C(i)=1$.

## 数学代写|计算复杂度理论代写Computational complexity theory代考|Alternating Turing Machines

(i) 的根吨在吨一个CC.
(ii) 如果在是一个内部存在节点吨一个CC，那么恰好是的一个孩子在在吨在吨一个CC.

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

SPACE Bounded Halting Problem (SBHP)：给定一个 DTM米, 一个输入X, 和一个整数s，写成一元形式0s, 判断是否米接受X在空间范围内s.

PSPACE 完全集的存在意味着如果多项式时间层次适当地无限，则 PSPACE 适当地包含磷H.

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

(i) 如果b=0， 然后C(一世)=C(j)⋅C(ķ);
(ii) 如果b=1， 然后C(一世)=C(j)+C(ķ);
(iii) 如果b=2， 然后C(一世)=0;
(iv) 如果b=3， 然后C(一世)=1.

## 有限元方法代写

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 环境以解决特定类别的问题。可用工具箱的领域包括信号处理、控制系统、神经网络、模糊逻辑、小波、仿真等。

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

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代考|NP-Complete Optimization Problems

Based on the notion of polynomial-time Turing reducibility, we can see that many important combinatorial optimization problems are $N P$-hard search problems. We prove these results by first showing that the corresponding decision problems are $\leq_{m}^{P}$-complete for $N P$ and then proving that the problems of searching for the optimum solutions are $\leq_{T}^{P}$-equivalent to the corresponding decision problems. In practice, however, we often do not need the optimum solution. A nearly optimum solution is sufficient for most applications. In general, the $N P$-hardness of the optimization problem does not necessarily imply the $N P$-hardness of the approximation to the optimization problem. In this section, we demonstrate that for some $N P$-complete optimization problems, their approximation versions are also $N P$-hard and, yet, for some problems, polynomial-time approximation is achievable. These types of results are often more difficult to prove than other $N P$-completeness results. We only present some easier results and delay the more involved results until Chapter $11 .$

We first introduce a general framework to deal with the approximation problems. Very often, an optimization problem $\Pi$ has the following general structure: for each input instance $x$ to the problem $\Pi$, there are a number of solutions $y$ to $x$. For each solution $y$, we associate a value $v_{\Pi}(y)$ (or, simply, $v(y)$, if $\Pi$ is known from the context) to it. The problem $\Pi$ is to find, for the given input $x$, a solution $y$ to $x$ such that its value $v(y)$ is maximized (or minimized). For instance, we can fit the problem MAXCLIQUE into this framework as follows: an input to the problem is a graph $G$; a solution to $G$ is a clique $C$ in $G$; the value $v(C)$ of a solution $C$ is the number of its vertices; and the problem is to find, for a given graph $G$, a clique of the maximum size.

Let $r$ be a real number with $r>1$. For a maximization problem $\Pi$ with the above structure, we define its approximation version, with the approximation ratio $r$, as follows:
$r$-APProx-П: For a given input $x$, find a solution $y$ to $x$ such that $v(y) \geq v^{}(x) / r$, where $v^{}(x)=\max {v(z): z$ is a solution to $x$.
Similarly, for a minimization problem $\Pi$, its approximation version with the approximation ratio $r$ is as follows:$r$-APPROX-П: For a given input $x$, find a solution $y$ to $x$ such that $v(y) \leq r \cdot v^{}(x)$, where $v^{}(x)=\min {v(z): z$ is a solution to $x}$.

## 数学代写|计算复杂度理论代写Computational complexity theory代考|Nondeterministic Oracle Turing Machines

We have defined in Chapter 2 the notions of polynomial-time Turing reducibility and oracle TMs, and have seen that many optimization problems, when formulated in the search problem form, are solvable in polynomial time relative to a set in $N P$. We now extend this notion to nondeterministic oracle TMs and study problems that are solvable in nondeterministic polynomial time relative to sets in $N P$.

A nondeterministic (function-)oracle Turing machine (oracle NTM) is an NTM equipped with an additional query tape and two additional states: the query state and the answer state. The computation of an oracle NTM is similar to that of an oracle DTM, except that at each nonquery state an oracle NTM can make a nondeterministic move. We require that the query step of the computation be a deterministic move determined by the oracle. Let $M$ be an oracle NTM and $f$ an oracle function. We write $M^{f}(x)$ to denote the computation of $M$ on input $x$, using $f$ as the oracle function (note that this is a computation tree). If the oracle function is a characteristic function of a set $A$, we say $M$ is a set-oracle NTM and write $M^{A}$ to denote $M^{f}$, and write $L(M, A)$ to denote the set of strings accepted by $M^{A}$.

The time complexity of a set-oracle NTM is also defined similar to that of a set-oracle DTM. In particular, the actions from the query state to the answer state count as only one step. For any fixed oracle set $A$, we let $\operatorname{time}{M}^{A}(x)$ be the length of the shortest accepting computation path of $M^{A}(x)$ and $t{M}^{A}(n)=\max \left({n+1} \cup\left{\operatorname{time}{M}^{A}(x):|x|=n, M^{A}\right.\right.$ accepts $\left.\left.x\right}\right)$. For a set-oracle NTM $M$, we say $t{M}(n)$ is bounded by a function $g(n)$, if for all oracle sets $A, t_{M}^{A}(n) \leq g(n)$. An oracle NTM $M$ is a polynomialtime oracle $N T M$ if $t_{M}(n)$ is bounded by a polynomial function $p$. Let $A$ be a set and $\mathcal{C}$ be a complexity class. We let $N P^{A}$ denote the class of sets accepted by polynomial-time oracle NTMs relative to the oracle $A$, and let $N P^{C}$ (or, $N P(\mathcal{C})$ ) denote the class of sets accepted by polynomial-time oracle NTMs using an oracle $B \in \mathcal{C}$ (i.e., $N P^{C}=\bigcup_{B \in C} N P^{B}$ ).

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

The polynomial-time hierarchy is the polynomial analog of the arithmetic hierarchy in recursion theory (Rogers, 1967). It can be defined inductively by oracle NTMs.

Definition $3.3$ For integers $n \in \mathbb{N}$, complexity classes $\Delta_{n}^{P}$, $\Sigma_{n}^{P}$, and $\Pi_{n}^{P}$ are defined as follows:
\begin{aligned} \Sigma_{0}^{P} &=\Pi_{0}^{P}=\Delta_{0}^{P}=P, \ \Sigma_{n+1}^{P} &=N P\left(\Sigma_{n}^{P}\right), \ \Pi_{n+1}^{P} &=c o-\Sigma_{n+1}^{P}, \ \Delta_{n+1}^{P} &=P\left(\Sigma_{n}^{P}\right), \quad n \geq 0 . \end{aligned}
The class $P H$ is defined to be the union of $\Sigma_{n}^{P}$ over all $n \geq 0$.
Thus, $\Sigma_{1}^{P}=N P, \Sigma_{2}^{P}=N P^{N P}, \Sigma_{3}^{P}=N P\left(N P^{N P}\right)$, and so on. It is easy to verify that these classes form a hierarchy.
Proposition 3.4 For all $k>0$,
$$\Sigma_{k}^{P} \cup \Pi_{k}^{P} \subseteq \Delta_{k+1}^{P} \subseteq \Sigma_{k+1}^{P} \cap \Pi_{k+1}^{P} \subseteq P S P A C E .$$
Proof. Note that $P^{A}=P^{\bar{A}}$, and so $\Pi_{k}^{P} \subseteq P\left(\Pi_{k}^{P}\right)=P\left(\Sigma_{k}^{P}\right)=\Delta_{k+1}^{P}$. Other inclusive relations among classes in $P H$ follow easily from the definition. Finally, the whole hierarchy $P H$ is included in $P S P A C E$ following from Proposition 3.2(b).

Based on the above proposition, we show in Figure $3.1$ the basic structure of the polynomial-time hierarchy. To further understand the structure of the polynomial-time hierarchy, we first extend Theorem $2.1$ to a characterization of the polynomial-time hierarchy in terms of the polynomiallength-bounded quantifiers.

First, we observe some closure properties of the polynomial-time hierarchy under the Boolean operations.

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

r-APProx-П：对于给定的输入X, 找到解决方案是至X这样在(是)≥在(X)/r, 其中 $v^{}(x)=\max {v(z): z一世s一个s○l在吨一世○n吨○X.小号一世米一世l一个rl是,F○r一个米一世n一世米一世和一个吨一世○npr○bl和米\π,一世吨s一个ppr○X一世米一个吨一世○n在和rs一世○n在一世吨H吨H和一个ppr○X一世米一个吨一世○nr一个吨一世○r一世s一个sF○ll○在s:rП−一个磷磷R○X−磷:F○r一个G一世在和n一世np在吨X,F一世nd一个s○l在吨一世○n是吨○Xs在CH吨H一个吨v(y) \leq r \cdot v^{}(x),在H和r和v ^ {} (x) = \ min {v (z): z一世s一个s○l在吨一世○n吨○x}$。

## 数学代写|计算复杂度理论代写Computational complexity theory代考|Nondeterministic Oracle Turing Machines

set-oracle NTM 的时间复杂度也与 set-oracle DTM 的定义类似。特别是，从查询状态到回答状态的动作仅计为一步。对于任何固定的预言机集一个，我们让时间⁡米一个(X)是最短接受计算路径的长度米一个(X)和t{M}^{A}(n)=\max \left({n+1} \cup\left{\operatorname{time}{M}^{A}(x):|x|=n, M ^{A}\right.\right.$接受$\left.\left.x\right}\right)t{M}^{A}(n)=\max \left({n+1} \cup\left{\operatorname{time}{M}^{A}(x):|x|=n, M ^{A}\right.\right.$接受$\left.\left.x\right}\right). 对于 set-oracle NTM米， 我们说吨米(n)受函数限制G(n), 如果对于所有的 oracle 集一个,吨米一个(n)≤G(n). 一个预言机 NTM米是多项式时间预言机ñ吨米如果吨米(n)以多项式函数为界p. 让一个是一个集合和C是一个复杂度类。我们让ñ磷一个表示多项式时间预言机 NTM 相对于预言机接受的集合类别一个， 然后让ñ磷C（或者，ñ磷(C)) 表示多项式时间预言机 NTM 使用预言机接受的集合类别乙∈C（IE，ñ磷C=⋃乙∈Cñ磷乙 ).

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

Σ0磷=圆周率0磷=Δ0磷=磷, Σn+1磷=ñ磷(Σn磷), 圆周率n+1磷=C○−Σn+1磷, Δn+1磷=磷(Σn磷),n≥0.

Σķ磷∪圆周率ķ磷⊆Δķ+1磷⊆Σķ+1磷∩圆周率ķ+1磷⊆磷小号磷一个C和.

## 有限元方法代写

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 环境以解决特定类别的问题。可用工具箱的领域包括信号处理、控制系统、神经网络、模糊逻辑、小波、仿真等。

## 数学代写|计算复杂度理论代写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 环境以解决特定类别的问题。可用工具箱的领域包括信号处理、控制系统、神经网络、模糊逻辑、小波、仿真等。

## 数学代写|计算复杂度理论代写Computational complexity theory代考|Universal Turing Machine

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代考|Universal Turing Machine

One of the most important properties of a computation system like TMs is that there exists a universal machine that can simulate each machine from its code.

Let us first consider one-tape DTMs with the input alphabet ${0,1}$, the working alphabet ${0,1, \mathrm{~B}}$, the initial state $q_{0}$, and the final state set $\left{q_{1}\right}$, that is, DTMs defined by $\left(Q, q_{0},\left{q_{1}\right},{0,1},{0,1, \mathrm{~B}}, \delta\right)$. Such a TM can be determined by the definition of the transition function $\delta$ only, for $Q$ is assumed to be the set of states appearing in the definition of $\delta$. Let us use the notation $q_{i}, 0 \leq i \leq|Q|-1$, for a state in $Q, X_{j}, j=0,1,2$, for a tape symbol where $X_{0}=0, X_{1}=1$ and $X_{2}=\mathrm{B}$, and $D_{k}, k=0$, lor a moving direction for the tape head where $D_{0}=\mathrm{L}$ and $D_{1}=\mathrm{R}$. For each equation $\delta\left(q_{i}, X_{j}\right)=\left(q_{k}, X_{\ell}, D_{h}\right)$, we encode it by the following string in ${0,1}^{*}$ :
$$0^{i+1} 10^{j+1} 10^{k+1} 10^{\ell+1} 10^{h+1} .$$
Assume that there are $m$ equations in the definition of $\delta$. Let code $e_{i}$ be the code of the $i$ th equation. Then we combine the codes for equations together to get the following code for the TM:
$$\text { code }{1} 11 \text { code }{2} 11 \cdots 11 \text { code }_{m} \text {. }$$
Note that because different orderings of the equations give different codes, there are $m$ ! equivalent codes for a TM of $m$ equations.

The above coding system is a one-to-many mapping $\phi$ from TMs to ${0,1}^{}$. Each string $x$ in ${0,1}^{}$ encodes at most one TM $\phi^{-1}(x)$. Let us extend $\phi^{-1}$ into a function mapping each string $x \in{0,1}^{}$ to a TM $M$ by mapping each $x$ not encoding a TM to a fixed empty TM $M_{0}$ whose code is $\lambda$ and that rejects all strings. Call this mapping $t$. Observe that $t$ is a mapping from ${0,1}^{}$ to TMs with the following properties:
(i) For every $x \in \Sigma^{*}, t(x)$ represents a TM;
(ii) Every TM is represented by at least one $\iota(x)$; and
(iii) The transition function $\delta$ of the TM $t(x)$ can be easily decoded from the string $x$.

We say a coding system $t$ is an emumeration of one-tape DTMs if $t$ satisfies properties (i) and (ii). In addition, property (iii) means that this enumeration admits a universal Turing machine. In the following, we write $M_{x}$ to mean the TM $\iota(x)$. We assume that $\langle\cdot, \cdot\rangle$ is a pairing function on ${0,1}^{*}$ such that both the function and its inverse are computable in linear time, for instance, $\langle x, y\rangle=0^{|x|} 1 x y$.

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

Diagonalization is an important proof technique widely used in recursive function theory and complexity theory. One of the earliest applications of diagonalization is Cantor’s proof for the fact that the set of real numbers is not countable. We give a similar proof for the set of functions on ${0,1}^{*}$. A set $S$ is countable (or, enumerable) if there exists a one-one onto mapping from the set of natural numbers to $S$.

Proposition $1.20$ The set of functions from ${0,1}^{}$ to ${0,1}$ is not countable. Proof. Suppose, by way of contradiction, that such a set is countable, that is, it can be represented as $\left{f_{0}, f_{1}, f_{2}, \cdots\right}$. Let $a_{i}$ denote the $i$ th string in ${0,1}^{}$ under the lexicographic ordering. Then we can define a function $f$ as follows: For each $i \geq 0, f\left(a_{i}\right)=1$ if $f_{i}\left(a_{i}\right)=0$ and $f\left(a_{i}\right)=0$ if $f_{i}\left(a_{i}\right)=1$. Clearly, $f$ is a function from ${0,1}^{*}$ to ${0,1}$. However, it is not in the list $f_{0}, f_{1}, f_{2}, \cdots$, because it differs from each $f_{i}$ on at least one input string $a_{i}$. This establishes a contradiction.

An immediate consequence of Proposition $1.20$ is that there exists a noncomputable function from ${0,1}^{}$ to ${0,1}$, because we have just shown that the set of all TMs, and hence the set of all computable functions, is countable. In the following, we use diagonalization to construct directly an undecidable (i.e., nonrecursive) problem: the halting problem. The halting problem is the set $K=\left{x \in{0,1}^{}: M_{x}\right.$ halts on $\left.x\right}$, where $\left{M_{x}\right}$ is an enumeration of TMs.
Theorem $1.21 K$ is r.e. but not recursive.
Proof. The fact that $K$ is r.e. follows immediately from the existence of the universal TM $M_{u}$ (Proposition 1.17). To see that $K$ is not recursive, we note that the complement of a recursive set is also recursive and, hence, r.e. Thus, if $K$ were recursive, then $\bar{K}$ would be r.e. and there would be an integer $y$ such that $M_{y}$ halts on all $x \in \bar{K}$ and does not halt on any $x \in K$. Then, a contradiction could be found when we consider whether or not $y$ itself is in $K$ : if $y \in K$, then $M_{y}$ must not halt on $y$ and it follows from the definition of $K$ that $y \notin K$ and if $y \notin K$, then $M_{y}$ must halt on $y$ and it follows from the definition of $K$ that $y \in K$.

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

We study, in this section, the relationship between deterministic and nondeterministic complexity classes, as well as the relationship between time- and space-bounded complexity classes. We show several different simulations of nondeterministic machines by deterministic ones.
Theorem $1.28$ (a) For any fully space-constructible function $f(n) \geq n$,
$$D T I M E(f(n)) \subseteq N T I M E(f(n)) \subseteq D S P A C E(f(n)) .$$
(b) For any fully space-constructible function $f(n) \geq \log n$,
$$D S P A C E(f(n)) \subseteq N S P A C E(f(n)) \subseteq \bigcup_{c>0} D T I M E\left(2^{f(n)}\right) .$$
Proof. (a): The relation DTIME(f(n)) $\subseteq \operatorname{NTIME}(f(n))$ follows immediately from the fact that DTMs are just a subclass of NTMs. For the relation $N T I M E(f(n)) \subseteq D S P A C E(f(n))$, we recall the simulation of an NTM $M$ by a DTM $M_{1}$ as described in Theorem 1.9. Suppose that $M$ has time complexity bounded by $f(n)$; then $M_{1}$ needs to simulate $M$ for at most $f(n)$ moves. That is, we restrict $M_{1}$ to only execute the first $\sum_{j=1}^{f(n)} k^{i}$ stages such that the strings written in tape 2 are at most $f(n)$ symbols long. As $f(n)$ is fully space constructible, this restriction can be done by first marking off $f(n)$ squares on tape 2 . It is clear that such a restricted simulation works within space $f(n)$.
$\mathrm{~ ( b ) : ~ A g a i n , ~ D S P A C E ( f ( n ) ) ~}$ $N S P A C E(f(n)) \subseteq \bigcup_{c>0} D T I M E\left(2^{c f(n)}\right)$, assume that $M$ is an NTM with the space bound $f(n)$. We are going to construct a DTM $M_{1}$ to simulate $M$ in time $2^{c f(n)}$ for some $c>0$. As $M$ uses only space $f(n)$, there is a constant $c_{1}>0$ such that the shortest accepting computation for each $x \in L(M)$ is of length $\leq 2^{c_{1} f(|x|)}$. Thus, the machine $M_{1}$ needs only to simulate $M(x)$ for, at most, $2^{c_{1} f(n)}$ moves. However, $M$ is a nondeterministic machine and so its computation tree of depth $2^{c_{1} f(n)}$ could have $2^{20(\text { a }}$ ) naive simulation as (a) above takes too much time.

To reduce the deterministic simulation time, we notice that this computation tree, although of size $2^{2^{2 \varphi(m))}}$, has at most $2^{O(f(n))}$ different configurations: Each configuration is determined by at most $f(n)$ tape symbols on the work tape, one of $f(n)$ positions for the work tape head,one of $n$ positions for the input tape head, and one of $r$ positions for states, where $r$ is a constant. Thus, the total number of possible configurations of $M(x)$ is $2^{O(f(n))} \cdot f(n) \cdot n \cdot r=2^{O(f(n))}$. (Note that $f(n) \geq \log n$ implies $\left.n \leq 2^{f(n)}\right)$

## 计算复杂度理论代考

0一世+110j+110ķ+110ℓ+110H+1.

代码 111 代码 211⋯11 代码 米.

(i) 对于每个X∈Σ∗,吨(X)代表 TM；
(ii) 每个 TM 至少由一个代表我(X); (
iii) 过渡函数dTM的吨(X)可以很容易地从字符串中解码X.

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

D吨我米和(F(n))⊆ñ吨我米和(F(n))⊆D小号磷一个C和(F(n)).
(b) 对于任何完全空间可构造函数F(n)≥日志⁡n,

D小号磷一个C和(F(n))⊆ñ小号磷一个C和(F(n))⊆⋃C>0D吨我米和(2F(n)).

(b): 一个G一个一世n, D小号磷一个C和(F(n))  ñ小号磷一个C和(F(n))⊆⋃C>0D吨我米和(2CF(n))， 假使，假设米是一个有空间限制的 NTMF(n). 我们将构建一个 DTM米1模拟米及时2CF(n)对于一些C>0. 作为米仅使用空间F(n), 有一个常数C1>0这样每个的最短接受计算X∈大号(米)有长度≤2C1F(|X|). 因此，机米1只需要模拟米(X)因为，至多，2C1F(n)移动。然而，米是一个不确定的机器，因此它的深度计算树2C1F(n)本来可以220( 一个 ) 上面 (a) 的幼稚模拟需要太多时间。

## 有限元方法代写

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 环境以解决特定类别的问题。可用工具箱的领域包括信号处理、控制系统、神经网络、模糊逻辑、小波、仿真等。

## 数学代写|计算复杂度理论代写Computational complexity theory代考|Models of Computation and Complexity Classes

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代考|Strings, Coding, and Boolean Functions

Our basic data structure is a string. All other data structures are to be encoded and represented by strings. A string is a finite sequence of symbols. For instance, the word string is a string over the symbols of English letters; the arithmetic expression ” $3+4-5$ ” is a string over symbols $3,4,5,+$, and -. Thus, to describe a string, we must specify the set of symbols to occur in that string. We call a finite set of symbols to be used to define strings an alphabet. Note that not every finite set can be an alphabet. A finite set $S$ can be an alphabet if and only if the following condition holds.

Property 1.1 Two finite sequences of elements in $S$ are identical if and only if the elements in the two sequences are identical respectively in ordering.
For example, ${0,1}$ and ${00,01}$ are alphabets, but ${1,11}$ is not an alphabet because 11 can be formed by either 11 or ( 1 and 1$)$.

Assume that $\Sigma$ is an alphabet. A set of strings over the alphabet $\Sigma$ is called a language. A collection of languages is called a language class, or simply a class.

The length of a string $x$ is the number of symbols in the string $x$, denoted by $|x|$. For example, $\mid$ string $\mid=6$ and $|3+4-5|=5$. For convenience, we allow a string to contain no symbol. Such a string is called the empty string, which is denoted by $\lambda$. So, $|\lambda|=0$. (The notation $|\cdot|$ is also used on sets. If $S$ is a finite set, we write $|S|$ to denote its cardinality.)

There is a fundamental operation on strings. The concatenation of two strings $x$ and $y$ is the string $x y$. The concatenation follows associative law, that is, $x(y z)=(x y) z$. Moreover, $\lambda x=x \lambda=x$. Thus, all strings over an alphabet form a monoid under concatenation. ${ }^{1}$ We denote $x^{0}=\lambda$ and $x^{n}=x x^{n-1}$ for $n \geq 1$.

The concatenation operation on strings can be extended to languages. The concatenation of two languages $A$ and $B$ is the language $A B={a b$ : $a \in A, b \in B}$. We also denote $A^{0}={\lambda}$ and $A^{n}=A A^{n-1}$ for $n \geq 1$. In addition, we define $A^{}=\bigcup_{i=0}^{\infty} A^{i}$. The language $A^{}$ is called the Kleene closure of $A$. The Kleene closure of an alphabet is the set of all strings over the alphabet.

## 数学代写|计算复杂度理论代写Computational complexity theory代考|Deterministic Turing Machines

Turing machines (TMs) are simple and yet powerful enough computational models. Almost all reasonable general-purpose computational models have been known to be equivalent to TMs, in the sense that they define the same class of computable functions. There are many variations of TMs studied in literature. We are going to introduce, in this section,

the simplest model of TMs, namely, the deterministic Turing machine (DTM). Another model, the nondeterministic Turing machine (NTM), is to be defined in the next section. Other generalized TM models, such as deterministic and nondeterministic oracle TMs, will be defined in later chapters. In addition, we will introduce in Part II other nonuniform computational models which are not equivalent to TMs.

A deterministic (one-tape) TM (DTM) consists of two basic units: the control unit and the memory unit. The control unit contains a finite number of states. The memory unit is a tape that extends infinitely to both ends. The tape is divided into an infinite number of tape squares (or, tape cells). Each tape square stores one of a finite number of tape symbols. The communication between the control unit and the tape is through a readlwrite tape head that scans a tape square at a time (See Figure 1.1).
A normal move of a TM consists of the following actions:
(1) Reading the tape symbol from the tape square currently scanned by the tape head;
(2) Writing a new tape symbol on the tape square currently scanned by the tape head;
(3) Moving the tape head to the right or left of the current square; and
(4) Changing to a new control state.

## 数学代写|计算复杂度理论代写Computational complexity theory代考|Nondeterministic Turing Machines

The TMs we defined in the last section are deterministic, because from each configuration of a machine there is at most one move to make, and hence, there is at most one next configuration. If we allow more than one moves for some configurations, and hence those configurations have more than one next configurations, then the machine is called a nondeterministic Turing machine (NTM).

Formally, an NTM $M$ is defined by the following information: states $Q$; initial state $q_{0}$; accepting states $F$; input symbols $\Sigma$; tape symbols $\Gamma$, including the blank symbol $\mathrm{B}$; and the transition relation $\Delta$. All information except the transition relation $\Delta$ is defined in the same form as a DTM. The transition relation $\Delta$ is a subset of $(Q-F) \times \Gamma \times Q \times \Gamma \times$ ${\mathrm{L}, \mathrm{R}}$. Each quintuple $\left(q_{1}, s_{1}, q_{2}, s_{2}, D\right)$ in $\Delta$ indicates that one of the possible moves of $M$, when it is in state $q_{1}$ and scanning symbol $s_{1}$, is to change the current state to $q_{2}$, to overwrite symbol $s_{1}$ by $s_{2}$, and to move the tape head to the direction $D$.

The computation of an NTM can be defined similar to that of a DTM. First, we consider a way of restricting an NTM to a DTM. Let $M$ be an NTM defined by $\left(Q, q_{0}, F, \Sigma, \Gamma, \Delta\right)$ as above. We say $M_{1}$ is a restricted DTM of $M$ if $M_{1}$ has the same components $Q, q_{0}, F, \Sigma, \Gamma$ as $M$ and it has a transition function $\delta_{1}$ that is a subrelation of $\Delta$ satisfying the property that for each $q_{1} \in Q$ and $s_{1} \in \Gamma$, there is at most one triple $\left(q_{2}, s_{2}, D\right)$, $D \in{\mathrm{L}, \mathrm{R}}$, such that $\left(q_{1}, s_{1}, q_{2}, s_{2}, D\right) \in \delta_{1}$. Now we can define the notion of the next configurations of an NTM easily: For each configuration $\alpha=$ $\left(q_{1}, x_{1}, y_{1}\right)$ of $M$, we let $\vdash_{M}(\alpha)$ be the set of all configurations $\beta$ such that $\alpha \vdash_{M_{1}} \beta$ for some restricted DTM $M_{1}$ of $M$. We write $\alpha \vdash_{M} \beta$ if $\beta \in \vdash_{M}(\alpha)$. As each configuration of $M$ may have more than one next configurations, the computation of an NTM on an input $w$ is, in general, a computation tree rather than a single computation path (as it is in the case of DTMs). In the computation tree, each node is a configuration $\alpha$ and all its next configurations are its children. The root of the tree is the initial configuration.

We say an NTM $M$ halts on an input string $w \in \Sigma^{*}$ if there exists a finite sequence of configurations $\alpha_{0}, \alpha_{1}, \ldots, \alpha_{n}$ such that
(1) $\alpha_{0}=\left(q_{0}, \lambda, w\right)$;
(2) $\alpha_{i} \vdash_{M} \alpha_{i+1}$ for all $i=0,1, \ldots, n-1$; and
(3) $\vdash_{M}\left(\alpha_{n}\right)$ is undefined (i.e., it is an empty set).

## 数学代写|计算复杂度理论代写Computational complexity theory代考|Deterministic Turing Machines

(1) 从磁带头当前扫描的磁带方格中读取磁带符号；
(2)在磁带头当前扫描的磁带方格上写入一个新的磁带符号；
(3) 将磁带头移动到当前方格的右侧或左侧；(
4) 转变为新的控制状态。

## 数学代写|计算复杂度理论代写Computational complexity theory代考|Nondeterministic Turing Machines

NTM 的计算可以定义为类似于 DTM 的计算。首先，我们考虑一种将 NTM 限制为 DTM 的方法。让米是由以下定义的 NTM(问,q0,F,Σ,Γ,Δ)如上。我们说米1是一个受限制的 DTM米如果米1具有相同的组件问,q0,F,Σ,Γ作为米并且有过渡功能d1这是一个子关系Δ满足对于每个q1∈问和s1∈Γ, 最多有一个三元组(q2,s2,D), D∈大号,R, 这样(q1,s1,q2,s2,D)∈d1. 现在我们可以轻松定义 NTM 的下一个配置的概念： 对于每个配置一个= (q1,X1,是1)的米，我们让⊢米(一个)是所有配置的集合b这样一个⊢米1b对于一些受限的 DTM米1的米. 我们写一个⊢米b如果b∈⊢米(一个). 作为每个配置米可能有多个下一个配置，在输入上计算 NTM在通常，它是一个计算树，而不是单个计算路径（就像在 DTM 的情况下一样）。在计算树中，每个节点都是一个配置一个它的所有下一个配置都是它的孩子。树的根是初始配置。

(1)一个0=(q0,λ,在);
(2) 一个一世⊢米一个一世+1对所有人一世=0,1,…,n−1; (
3)⊢米(一个n)是未定义的（即，它是一个空集）。

## 有限元方法代写

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 环境以解决特定类别的问题。可用工具箱的领域包括信号处理、控制系统、神经网络、模糊逻辑、小波、仿真等。

## 数学代写|计算复杂度理论代写Computational complexity theory代考|Order-Disorder Phase Transitions in the Agent Population

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代考|Order-Disorder Phase Transitions in the Agent Population

As discussed before, in the “information domain,” we can study the system by mapping strategies to spins. In addition, we can map the difference between winning

probabilities, of cooperators and defectors, to an external magnetic field: $h=$ $p_{c}^{b}-p_{d^{b}}^{b}$. In doing so, by the Landau theory, we can analytically identify an orderdisorder phase transition. Notably, we analyze the free energy $F$ of the spin system on varying the control parameter $m$ (corresponding to the magnetization $M$ )
$$F(m)=-h m \pm \frac{m^{2}}{2}+\frac{m^{4}}{4}$$
where the sign of the second term depends on the temperature, i.e., positive for $T_{s}>$ $T_{c}$ and negative for $T_{s}<T_{c}$; we remind that $T_{c}$ represents the temperature beyond which it is not possible to play the PD due to the high particle speed (according to our assumption). For the sake of clarity, we want to emphasize that the free energy is introduced in order to evaluate the nature of the final equilibrium achieved by the system. In particular, looking for the minima of $F$ allows to investigate if our population reaches the Nash equilibrium, or different configurations (e.g., full cooperation). Figure $3.5$ shows a pictorial representation of the phase transitions that can occur in our system, on varying $T_{s}$ and the external field $h$. Then, the constraints related to the average speed of particles, and to the distance between each group and the permeable wall, can be in principle relaxed, as we can imagine to extend this description to a wider system with several groups, where agents are uniformly distributed in the whole space. Now, it is worth to highlight that our results are completely in agreement with those achieved by authors who studied the role of motion in the PD and in addition are able to explain why clusters of cooperators emerge in these conditions. At the same time, we remind that, in this model, agents are “memory-aware,” while usually investigations consider agents that reset their payoff at each step.

## 数学代写|计算复杂度理论代写Computational complexity theory代考|The Role of the Temperature in the Spatial Public Goods Game

In this section, we aim to analyze the role of the temperature in the spatial PGG. Before to proceed, it is important to remind the reader that, in this section, the terms “temperature” and “noise” refer to the same concept. As discussed in Chap. 1 , the dynamics of this game are affected by a number of parameters and processes, namely, the topology of interactions among the agents, the synergy factor, and the strategy revision phase. We remind that the latter is a process that allows agents to change their strategy. Notably, rational agents tend to imitate richer neighbors, in order to increase the probability to maximize their payoff. By implementing a stochastic revision process, it is possible to control the level of noise in the system, so that even irrational updates may be observed. In particular, we study the effect of noise on the macroscopic behavior of a finite structured population. We consider both the case of a homogeneous population, where the noise in the system is controlled by tuning a parameter representing the level of stochasticity in the strategy revision phase, and a heterogeneous population composed of a variable proportion of rational and irrational agents. In both cases numerical investigations show that the PGG has a very rich behavior, which strongly depends on the amount of noise in the system and on the value of the synergy factor. In doing so, we aim to provide a description of the PGG by the lens of statistical physics, focusing in particular on the impact of noise in the population dynamics. Saying that rational agents are those that tend to imitate their richer neighbors, we can state that irrational agents are those that randomly change their strategy. In the case of a homogeneous population, the intensity of noise in the system is controlled by tuning the level of stochasticity of all agents during the SRP, by means of a global parameter (indicated by $K$ ) that represents the noise/temperature. Instead, in the case of a heterogeneous population, the noise is controlled by tuning the density of irrational agents in the population. Results indicate that tuning the level of noise to interpolate between configurations where agents fully utilize payoff information (low noise) to those where they behave at random (high noise) strongly affects the macroscopic behavior of a population.

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

In the case of well-mixed populations of infinite size, the behavior of the system can be predicted as a function of the synergy factor $r$ by studying the related Nash equilibria. In particular, when agents play in groups of $G$ players, two different absorbing states appear separated at a critical point $r_{\mathrm{wm}}=G$. The population falls into full defection for $rr_{\mathrm{wm}}$. Conversely, when agents are arranged in the nodes of a network, surprisingly some cooperators can survive for values of $r$ lower than $r_{\text {wm }}$. This effect, discussed in Chap. 1 , is known as network reciprocity. At the same time, the network structure allows a limited number of defectors to survive also beyond $r=r_{\mathrm{wm}}$. We refer to the two critical values of $r$ at which cooperators first appear and defectors eventually disappear from the population, respectively, as $r_{c 1}$ and $r_{c 2}$. It is worth mentioning that most investigations in EGT are performed by numerical simulations, and an analytical definition of the critical thresholds (i.e., $r_{c 1}$ and $r_{c 2}$ ) identified in networked topologies is missing. As a result, when studying EGT models by arranging agents in different spaces, the values of critical thresholds are achieved by Monte Carlo simulations (see Chap. 2). In a networked population, depending on the values of $r$ and on how agents are allowed to update their strategy, it is possible to observe different regimes: two ordered equilibrium absorbing phases, where only one strategy survives (either cooperation or defection), and an active but macroscopically stable disordered phase corresponding to the coexistence between the two species/strategies.

F(米)=−H米±米22+米44

## 有限元方法代写

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 环境以解决特定类别的问题。可用工具箱的领域包括信号处理、控制系统、神经网络、模糊逻辑、小波、仿真等。