Question

Recall that${\mathbf{NP}}^{\mathrm{SAT}}$ is the class of languages that are decided by nondeterministic polynomial time Turing machines with an oracle for the satisfiability problem. Show that .${\mathbf{NP}}^{\mathrm{SAT}}\mathbf{=}{\sum }_2\mathbf{P}$

Short answer

The above problem is solved using the definition of Turing Machine ‘M’ is a mathematical model of a hypothetical computing machine which can be a predefined set of rules based on a collection of input variables, determine the outcome.

Step-by-step solution

Showing that∑2P⊆NPSAT

Now, suppose a language L is decided by ${\sum }_2$alternating Turing machine M. Then that Turing machine performs some number of existential branching, followed by some number of universal branching.

Consider the sub-trees of the computation path whose roots are the first universal step along the path. For each such sub-tree, M is (by definition) performing a computation. Thus, it is deciding a language in$Co-NP$ (Note: it may possibly be a different language for each sub-tree, but it does not matter).

Now consider a nondeterministic machine S that behaves just as M does, but replaces each of the computation sub-trees discussed above with a deterministic computation by a machine in $P^{SAT}$(this is feasible because$Co-NP\subseteq P^{SAT}$ ). Note that this machine only contains one run of existential branches, each extended with a deterministic computation that uses an SAT oracle and runs in polynomial time.

If assume$a\left(n\right)$ be the maximum number of steps taken by the alternating machine before the universal branches start, and $p\left(n\right)$be the maximum number of steps taken by any of the $P^{SAT}$machines which have substituted for the universal branching, then the running time of S is bounded by $a\left(n\right)+p\left(a\left(n\right)\right)$. Note that the term is a composition of functions, because the $p\left(n\right)$sub procedures are computing with inputs that may be longer than n (but must be smaller than or equal to,$a\left(n\right)$ since only $a\left(n\right)$steps have been executed at the time the sub-procedures are used).

Therefore, both a and p polynomials, so is their composition. Hence, S is in$N{P}^{SAT}$

Showing thatNPSAT=∑2P

Suppose a language L is decided by a NP machine M with an SAT oracle.

Consider the following modification of M. At each step of M’s computation that depends on the result of an oracle query, replace the step with a nondeterministic “split" that guesses the answer to the query. Each branch of the “split" also writes down the queried formula and answer obtained. Thus, at every “leaf" node of the computation tree (whenever the computation terminates), the tape contains a record of all queries and answers which lead to that leaf. Finally, in order to preserve the proper accepting behaviour of M, replace each accepting “leaf" of M with a computation that checks that all the oracle.

This last computation can be done purely with a run of existential branches followed by a run of universal branches. First, an NP machine that determines SAT is used to check all the favourably answered queries. Second, all of the negatively answered queries are checked by running a $Co-NP$machine that decides UNSAT.

Finally, we check if the machine we produced actually exists.${\sum }_{2}P$ Clearly, the steps have been ordered so that all of the existential branches precede all of the universal branches. Now it is just required to check that the maximum branch length is polynomial with respect to the input. There are at most a polynomial number of oracle queries and replacing each of them with a branch that writes the formula and query result only lengthens the branch by a polynomial amount. Thus, the total branch lengthening caused by this replacement is only a polynomial time a polynomial. Since the “checking" step at the end is performed by a polynomial number of applications of NP and$Co-NP$ machines (each run on a formula that is at most polynomial larger than the original input), the total time taken for this “checking" step is polynomial as well. Therefore, the machine is in ${\sum }_{2}P$.