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

## 计算机代写|计算复杂度理论代写Computational complexity theory代考|Equivalence to alternating Turing machines

So far we have defined the alternating hierarchy in terms of logical formulas. Let’s continue by justifying the claim that this had something to do with alternating Turing machines.

An alternating Turing machine generalizes a nondeterministic Turing machine by allowing both $\mathrm{OR}$ and $\mathrm{AND}$ nondeterministic transitions. This produces a branching tree of computations, just as in a nondeterministic machine, but instead of applying the rule that the machine accepts if any branch accepts, we apply a more complicated rule that essentially corresponds to evaluating a game tree.

Each leaf node of the tree, corresponding to a halting configuration of the machine, is assigned a value true or false depending on whether that configuration accepts or rejects. A deterministic node (with exactly one successor) gets the same value as its successor. Nondeterministic OR nodes get the OR if their successors’ values, while nondeterministic AND nodes get the AND of their successors’ values. The machine as a whole accepts if and only if the root node gets the value true.

An alternating Turing machine can easily implement a sequence of quantifiers, by representing each $\exists$ quantifier as a sequence of OR branches and each $\forall$ quantifier as a sequence of AND branches, where following each branch the machine writes the next bit of the appropriate variable to a work tape. Given a $\boldsymbol{\Sigma}_k^p$ language, this requires $k$ layers of alternating $\mathrm{OR}$ and $\mathrm{AND}$ branches, followed by a deterministic polynomial-time computation. So we can represent $\boldsymbol{\Sigma}_k^p$ languages (and similarly $\boldsymbol{\Pi}_k^p$ languages) using alternating Turing machines with this restriction on branching.

In the other direction, suppose that we have an alternating Turing machine, where on each branch of the computation we have a sequence of OR branches, followed by AND branches, followed by OR branches, with at most $k$ such subsequences of branches of the same type and at most polynomially-many steps altogether on each branch. We would like to argue that the language decided by this machine is in $\boldsymbol{\Sigma}_k^p$.

## 计算机代写|计算复杂度理论代写Computational complexity theory代考|Equivalence to oracle definition

We generally don’t distinguish between the alternating and oracle versions of the polynomial-time hierarchy, because they give the same classes. This is a little surprising since the alternating version requires us to choose all of our quantified variables at once, while the oracle version lets us choose oracle queries interactively, but it turns out we can use the existential quantifier at the front of a $\Sigma_k^p$ formula to guess what queries we intend to make and then reject and discard any branches where we guessed wrong.

Before jumping into the full result, let’s show how this works for $\boldsymbol{\Sigma}_2^p=$ $\mathbf{N P}^{\mathrm{NP}}$. For the moment we will use $\boldsymbol{\Sigma}_2^p$ specifically to refer to the alternating definition of the class, which we can think of as all predicates of the form $\exists w_1 \forall w_2 M\left(x, w_1, w_2\right)$ where $w_1$ and $w_2$ have size polynomial in $|x|$ and $M$ is a polynomial-time-computable predicate.

Showing $\boldsymbol{\Sigma}_2^p \subseteq \mathbf{N P} \mathbf{N P}^{\mathbf{N P}}$ is trivial. Given a $\boldsymbol{\Sigma}_2^p$ formula $\exists w_1 \forall w_2 M\left(x, w_1, w_2\right)$, construct an NP $\mathbf{N P}$ machine that guesses $w_1$, then uses an oracle call to test if $\exists w_2 \neg M\left(x, w_1, w_2\right)$ holds. Accept if the oracle rejects and reject if the oracle accepts. This makes the computation accept if $\exists w_1 \neg \exists w_2 M\left(x, w_1, w_2\right) \equiv$ $\exists w_1 \forall w_2 M\left(x, w_1, w_2\right)$.

# 计算复杂度理论代考

## 计算机代写|计算复杂度理论代写Computational complexity theory代考|Equivalence to oracle definition

myassignments-help数学代考价格说明

1、客户需提供物理代考的网址，相关账户，以及课程名称，Textbook等相关资料~客服会根据作业数量和持续时间给您定价~使收费透明，让您清楚的知道您的钱花在什么地方。

2、数学代写一般每篇报价约为600—1000rmb，费用根据持续时间、周作业量、成绩要求有所浮动(持续时间越长约便宜、周作业量越多约贵、成绩要求越高越贵)，报价后价格觉得合适，可以先付一周的款，我们帮你试做，满意后再继续，遇到Fail全额退款。

3、myassignments-help公司所有MATH作业代写服务支持付半款，全款，周付款，周付款一方面方便大家查阅自己的分数，一方面也方便大家资金周转，注意:每周固定周一时先预付下周的定金，不付定金不予继续做。物理代写一次性付清打9.5折。

Math作业代写、数学代写常见问题

myassignments-help擅长领域包含但不是全部: