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

machine M which eventually halts within a polynomial time either on an acceptance
or on a rejection or on a failure state such that

1. there exists an integer d such that for any word x of length n and any running
of M on x , the machine halts within a time of at most n d
2. for any word x , the set of all possible final states when running M on x includes
either the acceptance or the rejection state, but not both
3. for any word x ,wehave x

L if and only if there exists a running of M on x
which halts on an acceptance state

∈

The question of whether co-NP is equal to NP or not, i.e. whether the decision problem
is symmetric in NP, is still open. It is also considered as one of the most important
problems in theoretical computer sciences.

8.3.3 Intractability

We recall that our goal is to formalize what a hard problem is in order to make secu-
rity rely on a hard problem. In complexity theory, this is the notion of intractability .
Although this is a quite intuitive notion, it should be emphasized that negative notions,
e.g. inability to solve a problem, is hard to define. We rather use reference problems
which are believed to be hard and we reduce one problem to the other.

. We say that
accepting L 1 reduces (in a Karp sense 5 ) in polynomial time to accepting L 2 if there
exists a function f over

Let be an alphabet and let L 1 and L 2 be two languages over

∗ which is algorithmically computable in polynomial time
and such that for any word x we have x

∈ L 1 if and only if f ( x ) ∈ L 2 . Two languages

are polynomially equivalent if they reduce to each other.

The case of the NP class is quite interesting. We say that a language L is NP-hard
if any L 0 ∈

NP reduces to L in polynomial time. We further say that L is NP-complete

if L NP. Actually, NP-complete languages are such that any language in NP reduces

to them. Therefore they have the greatest complexity in NP.

∈

As an example we mention the language SAT of all satisfiable Boolean formulas.
Informally, a Boolean formula is defined as a tree in which every inner node is labeled
by a Boolean gate AND, OR, or NOT (the latter gate being on nodes with degree one
only) and every leaf is labeled by a variable

v i . The formula is satisfiable if there exists
an assignment of all variables to true or false such that the root node is evaluated
to true . We assume that we have defined an efficient encoding rule over an alphabet
in order to represent a Boolean formula. As an example, we can use the prefix encoding

5

From the name of Richard Karp who was, e.g. with Stephen Cook, one of the pioneers in complexity theory
in the early seventies.