Elements of Complexity Theory - A Classical Introduction to Cryptography: Applications for Communications Security - page 221

rule over ={∪ , ∩ , ¬ , v , 0 , 1 } . For instance, x =∪∩¬ v0 ∪ v1v10 ∪¬ v10v1

represents

((NOT v 0 ) AND ( v 1 OR v 10 )) OR ((NOT v 10 )OR v 1 ) .

This can be satisfied by the assignment v 0 = v 1 = v 10 = true . Therefore the word x

is in SAT.

Obviously, SAT is in NP since we can easily make a polynomial time Turing
machine which, for every input x and a witness r which encodes an assignment of
variable, checks that x and r are syntactically correct and that the assignment r satisfies
x . The following result tells us how acceptance of SAT is hard.

Theorem 8.4 (Cook 1971 [47]). SAT is NP-complete.

The idea of the proof consists of taking any language in NP and the corresponding
nondeterministic Turing machine. We consider the possible running step histories of
the Turing machine as variables, and we define a Boolean formula which checks that
the running steps are feasible with the Turing machine. This way we transform any
word x into a Boolean formula f ( x ) in polynomial time, and x is in the language if
and only if f ( x )

∈

SAT.

8.3.4 Oracles and Turing Reduction

Let us define oracle Turing machines . An oracle is a Boolean function defined by
a language L which corresponds to the decision membership problem. An oracle is
“connected” to an input tape which contains a finite set of nonblank words. The input
tape contains a query and the oracle answers whether the query is in the language or
not. An oracle Turing machine is a Turing machine with an additional tape which is
the input of an oracle, and special states query , yes , and no . Each time the Turing
machine enters into the query state, it instantly moves to a yes or no state depending
on the answer of the oracle. (Thus the transition function of the finite automaton does
not need to be defined on the query state.) In other words, we use the oracle as a
subroutine which answers whether or not the query x i is in the language L .

Usually, we write L as a superscript. For instance, we can consider the class P L of
languages accepted by an oracle Turing machine, where the latter works in polynomial
time and has access to an oracle for the decision problem of membership in L .

We say that accepting a language L 1 reduces (in a Turing sense) in polynomial time
to accepting a language L 2 if L 1 ∈ P L 2 , i.e. if there exists an oracle Turing machine

with an oracle for membership in L 2 which accepts L 1 in polynomial time (see Fig. 2).
As an example, we have seen in Section 7.3.2 some Turing reductions related to the
problem of computing orders of elements in a group. For example, we have seen that we