Appendix A. Tutorial in Complexity Theory

The subsequent two appendices are brief introductions to only those areas of complexity and number theory that are used in this book. There are many good general introductions to both complexity and number theory.

From the point of view of classical mathematics problems in cryptography are trivial in the sense that they can be solved by finitely many trials. However, reduction to finitely many cases does not make much sense if the number of cases is unmanageable. If we are not able to decrypt a message within a certain time limit, we might as well forget the whole thing because, as time passes by, the situation might change entirely.

The time complexity of an algorithm is a function of the length of the input. An algorithm is of time complexity f{n) iff, for all n and all inputs of length n, the execution of the algorithm takes at most/(n) steps. If n is an integer, its length is the number of digits or bits in n. Of course, there might be slow and fast algorithms for the same problem. In some cases an unlimited speed-up is possible. It is difficult to establish lower bounds for complexity that is to show, for instance, that every algorithm for a certain problem is of at least quadratic time complexity.

Clearly, time complexity depends on the model for algorithms we have in mind. The number of steps becomes smaller if more work can be included in one step. However, fundamental notions such as polynomial time complexity are largely independent of the model. Of course, this concerns only models chosen with good taste. For instance, an abstract subroutine for testing the primality of a given number should not be included in one step!

To be more specific, we choose a Turing machine as our model for algorithms. A Turing machine operates in discrete time. At each moment of time, it is in a specific internal (memory) state, the number of all possible states being finite. A read-write head scans letters written on a tape one at a time. Every pair (q, a) determines a triple (q_l,a_i,m), where the q's are states, a's are letters and m ("move") assumes one of the three values "left", "right" or "no move". This means that, after scanning the letter a in state q, the machine goes to the state q^, writes in place of a (possibly a, = a) and moves the read-write head according to m.

If the read-write head is about to "fall off" the tape, that is, a left move is instructed when the machine is scanning the leftmost square of the tape, then a new blank square is added to the tape. The same holds true with respect to the right end of the tape. This capability of indefinitely extending the external memory can be viewed as a built-in hardware feature of every Turing machine.

The tape can be viewed both as a potentially infinite memory and an input and output channel. The input-output format is specified as follows. The machine begins its computation by scanning the leftmost letter of a given input word in a specific initial state. The computation ends if and when the machine reaches a specific final state. Then the machine halts and the word appearing on the tape constitutes the output. When reading the output some auxiliary letters can be ignored. The reader is referred to [Sal] for more formal definitions, as well as for a discussion concerning the generality of the model.

Now it is clear what a step means. We can define the time complexity function associated with a Turing machine A by

f_A(n) = max {m\A halts after m steps for an input w with |w| = n} .

We assume for simplicity that A halts, that is, reaches the final state for all inputs. Of course, this is not the case with respect to an arbitrary Turing machine. A Turing machine A is polynomially bounded iff there is a polynomial p(n) such that f_A(n) < p(n) holds for all n. The notation P is used for all problems that can be solved using a polynomially bounded Turing machine.

A problem is referred to as (computationally) intractable (sometimes also impossible) if it is not in P. Tractable problems (that is, problems in P) have several subclasses whose definition should be obvious: problems with linear, quadratic, cubic, etc. time complexity. The informal reference to a problem as easy means that the values of the polynomial are small, at least within the range considered.

The Turing machine considered above is deterministic: the scanned letter and the internal state determine the behavior uniquely. To emphasize that a determin­istic Turing machine is involved, we often speak of deterministic time complexity.

A nondeterministic Turing machine may have several possibilities for its behav­ior when scanning a specific letter in a specific state. Consequently, specific inputs give rise to several computations. This can be visualized as the machine making guesses or using an arbitrary number of parallel processors. For each input w, the shortest successful computation s(w) (that is, a computation leading to the final state) is considered. The time complexity function of a nondeterministic Turing machine A is now defined by

f_A(n) = max {1, m | s(w) has m steps for w with |w| = n} .

The pair (1, m) is considered because, for some n, possibly no inputs of length n lead to successful computations. The notions of a polynomially bounded nondetermin­istic Turing machine and the corresponding class of problems, NP, are now defined exactly as in the deterministic case.

Problems in P are tractable, whereas the problems in NP have the property that it is tractable to check whether or not a good guess for the solution of the problem is correct. A time bound for a nondeterministic Turing machine can be visualized as a time bound for checking whether or not a good guess for the solution is correct. It is not known whether the factorization of an integer is in P but it certainly is in NP: one just guesses the decomposition and verifies the guess by computing the product.

By definition, P is included in NP but it is a celebrated open problem whether or not P = NP. However, there are many NP-complete problems. A specific problem is NP-complete iff it is in NP and, moreover, it is NP-hard, that is, every problem in NP can be reduced in polynomial time to this specific problem. It follows that P = NP iff an NP-complete problem is in P. In such a case an arbitrary problem in NP can be settled in deterministic polynomial time because it can first be reduced in polynomial time to the specific NP-complete problem which, in turn, can be settled in polynomial time. Clearly, the composition of two polynomials is again a polynomial.

It is generally believed that P ^ NP. Therefore, JVP-complete problems are considered to be intractable. Besides NP, the terms "hard" and "complete" are used in a similar manner in connection with other classes of problems as well.

A specific problem is shown to be JVP-hard by proving that some problem previously known to be NP-hard can be reduced in polynomial time to the specific problem in question. If we want to show that the specific problem is NP-complete, we have to show also that it is in NP.

However, we need something to start with: a problem whose NP-completeness can be established by a direct argument, without any reductions. A problem very suitable for this purpose is the satisfiability problem for well-formed formulas of the propositional calculus, abbreviated wffpc's. Such a formula is obtained from vari­ables by using the operations conjunction a , disjunction v and negation ~ in a well-formed manner. We omit the obvious recursive definition. A truth-value assignment for a wffpc a is a mapping of the set of variables occurring in a into the set {true, false}. The truth-value of a can be computed for any truth-value assign­ment using the truth-tables of conjunction, disjunction and negation. Two wffpc's are equivalent iff they assume the same truth-value for all truth-value assignments. A wffpc a is satisfiable iff it assumes the value "true" for some truth-value assignment. For instance, the wffpc

(x, v ~ x₂ v x₃) a (x₂ v x₃) a ( ~ xj v x₃) a ~ x₃

is not satisfiable. Indeed, the last clause forces the assignment x₃ = false. Hence by the third clause, x, = false, and by the second clause x₂ = true. But this assignment contradicts the first clause. The wffpc considered is in conjuctive normal form: a conjunction of disjunctions, where the terms of each disjunction are literals, that is, variables or negated variables. Moreover, it is in 3-conjunctive normal form: each conjunctive clause contains at most three literals.

The satisfiability problem for wffpc's can be shown to be NP-complete by a direct argument. Indeed, the computation of a given Turing machine with a given input being successful is equivalent to a certain wffpc being satisfiable. The details can be found, for instance, in [Sal]. The result remains valid if attention is restricted to wffpc's in 3-conjunctive normal form. Satisfiability can, of course, be found out by checking through all possible truth-value assignments. This however, leads to exponential time complexity.

Space complexity is defined analogously. If a Turing machine receives an input of length n, then originally n tape squares are occupied. New squares may be needed during the computation; their number indicates the space complexity.

Polynomial bounds can be considered also now. This gives rise to the classes P-SPACE and NP-SPACE. Clearly, a time class is included in the corresponding space class because one time unit is needed to extend the tape by one square. For space classes one can actually prove that P-SPACE = /VP-SPACE. Consequently, we have the following chain of inclusions

P ^ NP c p-SPACE = NP-SPACE .

Whether or not the two inclusions are proper is a celebrated open problem.

The class Co-NP consists of problems whose "complement" is in NP. For instance, the complement of the problem "Is a given integer prime?" is "Is a given integer composite?" A formal definition can be given by considering problems as languages. It is clear that if a problem is in P, then also its complement is in P: the same algorithm works for the complement as well. This does not hold true in the nondeterministic case. In fact, the interrelation between NP and Co-NP is un­known but it is generally believed that NP # Co-NP. It is easy to see that if the complement of some /VP-complete problem is in NP, then NP = Co-NP.

There are some caveats to be kept in mind when complexity theory is applied to cryptography. When considering polynomial time complexity, the degree of the polynomial is certainly significant. For instance, n¹⁰⁰⁰ grows ultimately slower than n'^og'^og" but is still likely to be a much worse upper bound for the values under consideration. In cryptography average complexity is more important than worst case complexity. Suppose a user chooses at random the encryption key in a public- key cryptosystem. It is then insignificant if computing the corresponding decryp­tion key is intractable in some rarely occurring cases but easy in most cases.

Probabilistic or stochastic algorithms are often used in cryptography. Intuit­ively this means that random choices are made (that is, a random number gener­ator can be called) at certain stages during the execution of the algorithm. The terminology introduced above is extended to concern the stochastic case. Thus, we may speak of algorithms running in random polynomial time. The corresponding class of problems is often denoted by BP P. It is generally believed that BPP # NP. Stochastic algorithms may fail but the probability of failure can be made arbitrarily small. Usually the time complexity increases when the probability of failure becomes smaller. The failure is due to the stochastic element. The following terminology is used to indicate different types of failure. A Monte Carlo algorithm might give a wrong answer in some cases. A Las Vegas algorithm always gives a correct answer, but it might end up with the answer "I don't know" in some cases.

We mention finally that, when talking about time complexity, we usually do not consider the computation steps of a Turing machine but rather some other elementary operation such as bit multiplication. The classes P and NP are invari­ant under such changes but, for instance, the degree and/or coefficients of the polynomial involved may change.

Date: 2015-02-16; view: 777