Complexity and Cryptography: An Introduction

---

Astasia Carla Pagnoni rated it it was amazing Dec 27, Eugene added it Apr 22, Daniel added it Aug 05, Ben added it Aug 31, Huyichen marked it as to-read Sep 07, Rashmi Wadbude added it Mar 11, Ghazal Marine marked it as to-read Jul 07, Rafik Hamza marked it as to-read Aug 26, Nitin CR added it Nov 12, Jeremy Czech marked it as to-read Jan 16, Denis marked it as to-read Jun 05, Abdulaziz marked it as to-read Sep 01, Jonathan marked it as to-read Mar 06, Zvr added it May 17, Deej Roth marked it as to-read Jan 09, Ernie marked it as to-read Aug 14, Starfighter marked it as to-read Dec 29, Elizabeth Aedyn River marked it as to-read Mar 05, There are no discussion topics on this book yet.

If you like books and love to build cool products, we may be looking for you. Books by John Talbot. Trivia About Complexity and Cr No trivia or quizzes yet. Just a moment while we sign you in to your Goodreads account. A far more natural encoding is binary. For example, the number 49 is encoded as rather than or A bit is simply a binary digit, so for example 49 is a 6-bit integer, since the binary encoding of 49 contains 6 binary digits.

In order to describe a binary addition algorithm we introduce a function sum a, b, c that takes three binary digits as its input and outputs their sum. Again it is easy to check that this algorithm works, but how does it compare to our previous algorithm in terms of efficiency? Our algorithm performs n iterations of the while loop and on each iteration it performs six operations. This compares very favourably with our previous algorithm. This highlights another key idea. The guiding principle being that the encoding should describe the input as succinctly as possible.

This will always be the length of the natural encoding of the input. Since the running time of most algorithms depends on the size of the input it is natural to consider the performance of an algorithm in terms of its running time over all inputs of a fixed size. There are two obvious ways one might do this.

We could consider either the average-case running time or the worst-case running time. The vast majority of work in complexity theory deals with worstcase analysis and we will always take this approach. See Levin for a succinct introduction to average-case complexity theory.

Consider the following basic algorithm for testing whether an integer is prime. This depends very much on the input N. For an explanation of the O-notation see Appendix 1. The obvious question to ask is whether this is efficient? As the size of our input increases the running time of this algorithm grows exponentially. Such an algorithm is clearly highly impractical: This is not only beyond the limits of modern computers but arguably beyond the reach of any that we could envisage.

Yet to use some modern cryptosystems we must be able to test the primality of such numbers. We need an algorithm whose running time does not grow exponentially as the input size increases. An obvious growth rate that is much slower than exponential is polynomial. Moreover most of the algorithms that have proved useful in real situations share the property that their running time is polynomial.

This observation provides us with our fundamental notion of a practical algorithm. Hence, if a problem has an algorithm whose running time grows polynomially with the input size then we consider the problem to be tractable. Justification for this is provided in the table below. This demonstrates how, as the input size grows, any exponential time algorithm quickly becomes impractical, while polynomial time algorithms scale reasonably well.

A word of caution: To proceed any further we require a formal model of computation. In the next section we describe the classical example of such a model: Sorting n integers a1 ,. The transition function tells the machine what to do next given the contents of the current square and the current state of the control unit. If the machine never enters a halting state then the computation does not finish, otherwise the computation ends when a halting state is reached.

A single application of the transition function is called a step. A configuration of a DTM is a complete description of the machine at a particular point in a computation: We say that a DTM computes a function f: To give an idea of what a DTM looks like we give a simple example: We represent the transition function by a list of quintuples.

The first two entries of each quintuple represent the current state and the content of the current square, while the last three entries represent the new state, the new symbol to write in the current square and the movement left or right of the read—write head. In an attempt to make the machine description more readable we place comments marked by next to each instruction.

The obvious way to measure time on a DTM is as the number of steps the machine takes before halting. Previously we saw algorithms for unary and binary addition and in those cases the binary addition algorithm was far more efficient. So a natural question to ask is how does this unary addition DTM compare with a DTM that performs addition of integers with the input encoded in binary?

Our binary addition DTM see Algorithm 2.

See a Problem?

It takes the two least significant bits of a and b and forms the next bit of the answer, while storing a carry bit on the front of the answer. To get an idea of how it works try an example. Note that in Algorithm 2. One obvious difference between our two DTMs is that using binary encoding for the input results in a far more complicated machine, but which is more efficient?

The machine does this k times, once for each bit in a. Finally it erases the equals and plus signs. For large inputs this machine is clearly much more efficient as the table in Figure 2. Having compared the running time of these two machines we introduce the formal definitions of time complexity. We denote this by t M x. Recall that we wish to assess the efficiency of an algorithm in terms of its worst-case behaviour. In practice we will rarely want to work directly with Turing machines.

Higher level descriptions of algorithms, such as the binary addition algorithm given in Algorithm 2. We will consider the running times of different algorithms to be similar if they differ only by a polynomial factor. Consider the example of binary addition. In our high-level version, Algorithm 2. Thus, for this example at least, our model is robust. Since we consider an algorithm to be practical if and only if it has polynomial running time, our assumption that the DTM model of computation is robust can be phrased as follows. That is it takes a string of n ones and replaces it by two strings of n ones, separated by a blank square.

What is the time complexity of your machine? For example the problem of deciding if a number is prime. This is an example of a decision problem. We introduce a special type of DTM that is particularly useful for examining such problems. These should be thought of as corresponding to true and false respectively.

There is an obvious correspondence between languages accepted by acceptor DTMs and decision problems. Note that in order to obtain this correspondence we needed to choose a natural encoding scheme for the input to the decision problem, in this case binary. Complexity classes and P The aim of complexity theory is to understand the intrinsic difficulty of computational problems. When considering a decision problem a natural way to measure its difficulty is to consider the time complexity of machines that decide the associated language. Since we wish to classify problems in terms of their relative and hopefully absolute difficulty, we will be interested in collections of languages which can all be decided by DTMs with the same bound on their time complexity.

Any such collection of languages is called a complexity class. A fundamental complexity class is the class of polynomial time decidable languages, or P. In the remainder of this chapter we will consider some of the most important examples, mainly from the fields of logic and graph theory. SATisfiability The classic example of a decision problem is Boolean satisfiability. A Boolean function is a function f: A literal is a Boolean variable or its negation. The conjunction of a collection of literals x1 ,. The disjunction of a collection of literals x1 ,.

A Boolean function, f , is said to be in conjunctive normal form or CNF if it is written as f x1 ,. For example consider the following two Boolean functions f x1 ,. Of these f is in CNF but g is not. A truth assignment for a Boolean function, f x1 ,. If such an assignment exists then f is said to be satisfiable. Boolean satisfiability, otherwise known as SAT, is the following decision problem.

We require a natural encoding scheme for this problem. For example the formula f x1 ,. Since no clause can contain more than 2n literals the input size of a CNF formula with n variables and m clauses is O mn log n. Clearly the problem 1-SAT is rather easy. Any satisfying truth assignment for f in this case must set every literal appearing in f to be true.

Thus f is satisfiable if and only if it does not contain both a literal and its negation. Graph problems Another source of important decision problems is graph theory. For basic definitions and notation see Appendix 2. Obvious real world problems related to graphs include the travelling salesman problem, tree alignment problems in genetics and many timetabling and scheduling problems.

An Introduction

As before we need to describe a natural encoding scheme for graphs. There are two obvious ways to encode this on a DTM tape. We could use the adjacency matrix, A G. With this encoding scheme the input size would be O n 2. An alternative way to encode a graph is via a list of edges. In this case the input size would be O m log n.

Which of these two encodings is shorter depends on how many edges are present in the graph. However, unless the graphs we are considering contain very few edges the input size of the two encodings will differ only by a polynomial factor. So if we are only interested in whether an algorithm has polynomial running time then we will be able to work with whichever encoding scheme is more convenient.

It asks whether or not a graph contains a clique of order k. That is a collection of k vertices among which all possible edges are present. In such cases we have to be careful to correctly identify the input size. We follow the obvious rule that the input size is the sum of the input sizes of the various parts of the input. Hence k n the total number of edges checked by the algorithm is at most 2 k.

Since k is a constant that is independent of the input the running time of this algorithm is O n k which is polynomial in n. In Chapter 3 we will see why this is such an important question. A k-colouring is an assignment of k colours to the vertices of a graph G such that no edge joins two vertices of the same colour. Formally it is a function f: A graph G is said to be k-colourable if and only if a k-colouring of G exists. Questions related to colourings of graphs are another source of important decision problems. This is very straightforward. We noted earlier that 1-SAT trivially belongs to P.

Our next result tells us that 2-SAT also belongs to P, but this requires a little more work. It corresponds in an obvious way to the concept of a subroutine in a computer program. Suppose f x1 ,. Then each clause, Ck , is the disjunction of at most two literals. Consider the following decision problem for digraphs. We will prove a below but b is left as a simple exercise.

We can now describe a polynomial time algorithm for 2-SAT. First define a function r: But why is this a polynomial time algorithm? Hence this is a polynomial time algorithm. We now give a proof of claim a. We will show that in this case f is unsatisfiable since no truth value can be chosen for xi. The two directed paths imply that the following clauses belong to f: The clauses in the first row imply that xi cannot be true while those in the second row imply that xi cannot be false.

Hence f is unsatisfiable. For a literal a we define R a to be the literals which can be reached by directed paths from a together with a itself. We also define R a to be the negations of the literals in R a. We construct a satisfying truth assignment using the following procedure.

If we did then there would exist directed paths from a to v and from a to v. But G f has the property that there is a directed path from c to d if and only if there is a directed path from d to c. Hence in this case there would be a 30 2 Complexity theory directed path from v to a. For example, consider the function fac n: An efficient algorithm for computing fac n would break many of the most commonly used cryptosystems. For this reason determining the complexity of this function is an extremely important problem.

In order to discuss such questions we need to extend our definitions of complexity to functions. In fact all of the basic integer arithmetic operations are polynomial time computable. Our next result is a proof of this for multiplication. First note that multiplication by two is easy to implement. For a binary integer a we simply shift all of its digits left by a single place and add a zero to the right of a. Consider the following algorithm. It is easy to see that this algorithm works. The fact that it runs in polynomial time follows simply from the observation that the for loop is repeated at most n times and each line of the algorithm involves basic polynomial time operations on integers with at most 2n bits.

We can avoid this problem if we work modulo an integer c. We will use the following algorithm. The for loop is repeated m times so the whole algorithm is polynomial time. It is easy to check that this algorithm is correct. For integers c and d we denote the fact that c divides d exactly by c d. To complete the proof we need to show that this is a polynomial time algorithm. Each line of Algorithm 2.

We simply need to prove that the number of times the while loop is repeated is bounded by a polynomial in the input size: Another resource that limits our ability to perform computations is space. We now introduce the necessary definitions to discuss the space complexity of a DTM. We denote this by s M x. Clearly space is a more valuable resource than time in the sense that the amount of space used in a computation is always bounded above by the amount of time the computation takes. The number of squares examined by the read—write head of any DTM cannot be more than the number of steps it takes.

Our next theorem tells us that although space may be more valuable than time, given an exponential amount of time we can compute anything that can be computed in polynomial space. There are k possibilities for i and, since the computation uses at most p n tape squares, there are at most p n possibilities for ii. Hence in total there are kp n m p n possible configurations for M during its computation on input x. Can any of these configurations ever be repeated? Clearly not, since if they were then the machine would have entered a loop and would never halt. Show that for n sufficiently large f n satisfies p n 2.

Describe a DTM for deciding unary divisibility. That is it takes input a, b in unary and accepts if a divides b exactly otherwise it rejects. Consider the following generalisation of a DTM. A k-tape DTM is a machine with k tapes and k corresponding read—write heads one for each tape. The transition function now takes the current machine state, and the contents of the k squares currently scanned by the k read—write heads and returns the new state for the machine, the new symbol to write in each of the k current squares and the movements left or right of the k read—write heads.

Describe a 3-tape DTM for binary integer multiplication. What is the time complexity of your machine in O-notation? As before a single step is one application of the transition function. A Boolean formula f x1 ,. Show that the following problem belongs to P. Consider the following method for integer multiplication. Let Mn denote the time taken to multiply two n-bit integers using this method. What upper bound can you give for the time required to decide L? This is defined to be the number of times M writes a new non-blank symbol in a square.

Turing and their equivalence to other classical notions of computability resulting in the Church—Turing thesis was a major part of recursion theory; see for example the classical text by Rogers The origins of complexity theory can be traced back to Hartmanis and Stearns though the notion of P as a fundamental class is generally attributed to Cobham and Edmonds We note that some large instances up to 25 cities of the Travelling Salesman Problem TSP have been solved using cutting plane methods. See Dantzig, Fulkerson and Johnson and Applegate et al. However, no TSP algorithm is known which is guaranteed to always perform less than 2n operations on an input of n cities.

Unfortunately there are no known algorithms for SAT that perform significantly better. A naive explanation for this is that the obvious way to show that a formula f is satisfiable is to find a satisfying truth assignment. But there are too many possible truth assignments to be able to check them all in polynomial time. Consider some of the other decision problems we have seen so far. For example, a search algorithm for 3-COL could simply consider all 3n possible 3-colourings of a given graph, and check to see if any of them are legal. Again this would give an exponential time algorithm.

But why are these algorithms so slow? Given a possible truth assignment for an instance of SAT we can quickly check whether it is satisfying. These algorithms have exponential running time because in the worst case they need to check an exponential number of possible truth assignments or colourings. However, if a given instance of SAT is satisfiable then we know there must exist a satisfying truth assignment.

Equally, if a graph is 3-colourable then a legal 3-colouring of it must exist. Previously we considered algorithms for solving decision problems. In this chapter we consider a different type of question. One way of looking at this question is to consider the following hypothetical situation. Suppose we had an instance, f x1 ,.

Could we convince a sceptical observer of this fact in a reasonable amount of time? Certainly, simply give the observer the instance f together with a satisfying truth assignment x. Where this truth assignment has come from is not our concern, the important point is that if f is satisfiable then such a truth assignment must exist. Our observer could then check that this truth assignment satisfies f. Thus a satisfying truth assignment is a succinct certificate for the satisfiability of f , since it certifies that f is satisfiable and can be checked quickly. As we have already noted, many decision problems have obvious succinct certificates.

It is important to emphasise that the certificate being checked in each of the above examples need not be found in polynomial time. We are simply asserting that, if an instance of a particular decision problem is true, then there exists a succinct certificate which when presented to a sceptical observer allows him or her to verify in polynomial time that a particular instance of the problem is true.

In this case a succinct certificate proving that a particular integer n is composite is a proper, non-trivial factor of the input. Given such a factor we can easily check in polynomial time that 3. Our sceptical observer could use the following polynomial time checking algorithm in this case. If n is composite then for a suitable choice of d the checking algorithm will verify this fact.

However, if n is prime then no matter what value of d is given to the checking algorithm it will always output false. Moreover this is clearly a polynomial time algorithm. It is important to note that we cannot deduce that a number n is prime simply because this checking algorithm, when given n and a particular possible factor d, gives the answer false.

If n is composite but d is not a factor of n then this algorithm will output false. We are simply claiming that if this checking algorithm is given a composite integer n together with a factor d then it will output true and furthermore if n is composite then such a factor exists. We can formalise this definition as follows. However, this is currently one of the most important open problems in theoretical computer science.

How much larger can NP be than P? Our next result says that any language in NP can be decided in polynomial space. We simply try each possible certificate in turn. Since any possible certificate is of polynomial length, we can check all possible certificates using a polynomial amount of space by reusing the same tape squares for successive certificates. We also need some tape squares to store x and the current possible certificate y at each stage so that we can restart the next stage of the computation with the string x z where z is the next possible certificate after y.

In each case say whether or not you believe it also belongs to P. Consider the following decision problem. Recall that an independent set in a graph is a collection of vertices containing no edges. This is the graph on the same vertex set as G but with an edge present in G c if and only if it is missing from G. It will return the answer true if and only if the original graph contained an independent set of order k. We formalise this idea of a polynomial time reduction as follows. We now construct a polynomial time DTM which will decide A.

We then pass f x to N and accept or reject according to whether N accepts or rejects f x.

To see that it runs in polynomial time we note that the time taken to compute f x by M is at most p n. Our next result says that if B is at least as difficult as A, and C is at least as difficult as B, then C is at least as difficult as A. By this we mean do there exist examples of languages that belong to NP and which are at least as difficult as any other language in NP.

The fact that such languages exist is probably the most important result in complexity theory. The fact that most languages arising in practice that belong to NP but which are not known to belong to P are in fact NP-complete makes this even more intriguing. Before proving the existence of NP-complete languages we give two results showing how important NP-complete languages are. The first says that determining the true difficulty of any NP-complete language is an incredibly important question since if any NP-complete language is tractable then they all are. Suppose L is NPcomplete and also belongs to P.

This follows directly from Lemma 3. It provides a very natural example of an NP-complete language. Before giving the proof of Theorem 3. The following language is NP-complete. In order to do this we need to give a more natural example of an NP-complete language. Proof of Theorem 3. We think of these variables as having the following meanings when they are true: In order to construct the groups of clauses we will frequently wish to ensure that exactly one of a collection of variables, say z 1 ,.

At any time t exactly one tape square is scanned by the read—write head: At any time t each tape square contains exactly one symbol: At any time t the machine M is in a single state: It is easy to see that if we define Sx to be the Boolean formula given by the conjunction of all the above collections of clauses we have an instance of SAT. Moreover it is not too difficult to check that the size of Sx is polynomial in the input size. You can check that the number of variables in Sx is O p n 2 and the total number of clauses is O p n 3.

Given a satisfying assignment for Sx we can actually read off a good certificate: Indeed many thousands of languages associated to decision problems from many different areas are now known to be NP-complete. Recall the decision problem k-SAT from the previous chapter. Thus, by Proposition 3. We show this using a method known as local replacement: Given an instance of SAT f x1 ,. If we can prove these two claims then we will have shown that there is a function g: We now need to prove the two claims. The first part is easy.

Take a satisfying truth assignment for Di.

Complexity and Cryptography: An Introduction

This contradiction proves i. Hence ii also holds. Given an instance of 3-SAT f x1 ,. The graph G f has two vertices for each variable: The edges of G f are as follows: We claim that G f is 3-colourable if and only if the formula f has a satisfying truth assignment. Suppose first that G f is 3-colourable.

This gives an obvious truth assignment for f which we will now show is satisfying. However, if we consider Figure 3. Hence f is satisfied by this truth assignment. Conversely suppose that f is satisfiable. Take a satisfying truth assignment and consider the partial colouring of G f that it yields. So we colour the vertices xi , x i , R, T, F in the obvious way with the colours 0, 1 and red. This shows that G f is 3-colourable as required. We also noted that the polynomial time algorithm we gave had running time O n k and did not yield a polynomial time algorithm for the problem CLIQUE.

The following result explains why such an algorithm may be impossible to find. Given an instance of SAT, f x1 ,. The number of vertices in V G f is simply the number of literals in f counted according to the number of clauses they appear in, so this is O f. Hence this is a polynomial time construction. Suppose that f is a satisfiable instance of SAT. Conversely suppose G f has a clique of order m, then the vertices in the clique are a1 , 1 ,.

Setting each ai to be true gives a satisfying truth assignment for f , since each clause is now satisfied. For example in the proof of Proposition 2. This more general type of reduction is often very useful and indeed is the reduction commonly used in practice, such as when an algorithm calls a subroutine repeatedly. Informally a function f is Turing-reducible to a function g if a polynomial time algorithm for computing g would yield a polynomial time algorithm for computing f. To describe Turing-reducibility more precisely we introduce a new type of Turing machine: Such a machine has an extra tape known as the query tape and a special state: There is also an oracle function O associated with the machine.

First, it can read and write to the query tape. The output of a DOTM is, as before, the contents of the ordinary tape once the machine halts. Simply replace each call to the oracle for f by a call to a subroutine using the polynomial time algorithm. Recall the graph decision problem.

It is interesting to note that it is currently not known whether the notion of Turing-reduction is strictly more powerful than polynomial reduction when considering problems in NP. The most important example of such a class is co-NP, the collection of complements of languages in NP. For a decision problem the complementary language has a very natural interpretation: But what about SAT itself?

After a few moments thought it appears that the only way to convince a sceptical observer that an instance of SAT is unsatisfiable is by asking the observer to check every possible truth assignment in turn and verify that none of them are satisfying, but this is 3. This highlights an important difference between the classes P and NP.

For NP this is no longer the case. The question of whether NP and co-NP are equal is probably the second most important open problem in complexity theory, after the P versus NP question. Given an integer n it is far from obvious how one would convince a sceptical observer that n is prime in polynomial time.

There is no immediately obvious succinct certificate for primality. The fact that such a certificate does in fact exist is given by a classical theorem of Pratt In fact far more is true, we have the following outstanding result due to Agrawal, Kayal and Saxena We will however give a proof of the weaker Theorem 3.

For definitions see Appendix 3. We need to describe a succinct certificate for the fact that an integer n is prime. If n is a prime then, by Appendix 3, Theorem A3. Finally Appendix 3, Theorem A3. We will use this to describe a succinct certificate for the primality of a prime n.

We will not require a certificate for the primality of 2 since our checking algorithm will recognise this automatically. At this point it should be clear that if n is prime then there exists a certificate C n which this algorithm will accept. While if n is composite then no matter what certificate is given, Algorithm 3. In order to complete the proof we need to verify that this is a polynomial time algorithm.

Recall that the input is an integer n and so the input size is O log n. Hence, with the possible exception of the line checking the certificate C pi , each line of Algorithm 3. We will measure the time taken by this algorithm by the total number of lines of the algorithm that are executed; we denote this by f n. Note that when a certificate C pi is checked we imagine a new version of the algorithm starts and count the number of lines executed accordingly. We have seen plenty of examples of languages that either are NP-complete or belong to P.

Also the complement of any NP-complete language is clearly co-NP-complete so we could easily give lots of examples of such languages. One such example is given by the following decision problem. However, for completeness we introduce them now. Instead of a transition function it has a transition relation, so that at any point in a computation there are a number of possible actions it can take and it chooses one of these non-deterministically.

Given the content of the tape square currently being scanned, together with the current state of the machine, an NTM has a choice of possible actions, one of which is chosen non-deterministically. This determines what to write in the current square; the new state for N and the movement of the read-write head. Note that for any given input x there will typically be more than one possible computation. Such a computation is called an accepting computation. From now on we will consider only halting NTMs. Similarly to the case for a DTM a step in a computation is simply the result of applying the transition relation once.

The set of possible computations of an NTM on a particular input can easily be represented by a tree. A single possible computation is a path from the root to a leaf. Assuming that the machine is halting every possible computation is finite and so the tree is also finite. The key idea is to consider the computation tree of a polynomial time NTM. At any node in the tree there are a finite number of choices for the transition to the next stage. Hence we have the following theorem. In each case explain why it is difficult to produce a suitable certificate.

Consider the following problem. Prove that any two NP-complete languages are Turing equivalent. Is the containment strict? Further notes The notions of both polynomial and Turing reducibility were familiar tools in recursive function theory, as was the notion of nondeterminism.

The class of languages NP was introduced in by S. Karp then used SAT to show that 21 other natural problems were NP-complete under polynomial reductions. Independently Levin developed a similar theory using tilings rather than satisfiability, with the result that Theorem 3. The book by Garey and Johnson contains a vast array of NP-complete problems from a wide range of disciplines. Whether it will lead to a fast practical deterministic algorithm for testing primality is a question of ongoing research interest. It is now more than twenty years since Luks showed that testing graph isomorphism for graphs of degree at most d is polynomial for any fixed d.

The algorithm of Luks is polynomial in the number of vertices but exponential in d. However, before formalising this concept of a probabilistic or randomised algorithm we consider a simple example. We have to be careful about how the polynomials are presented so that we know how to measure the input size. For example the following polynomial f x1 ,.

However, if we expanded the parentheses this same polynomial would then seem to have input size O n2n log n. The degree of a polynomial is simply the maximum number of variables, counted according to their multiplicities, occuring in a single term when the polynomial is expressed in its expanded form. Intuitively this algorithm should work very well. If f is not identically zero then we will only output false if we accidentally choose a root of f , which seems rather unlikely. However, if after repeating this a hundred times with independent random choices for a1 ,.

An interesting point to note is that Algorithm 4. The important difference is that we do not try every possible certificate. Instead this algorithm simply chooses one possible certificate at random and checks to see if it is good. The intuitive reason why this works is that if the input polynomial is not identically zero then there are lots of good certificates and the probability that a randomly chosen certificate is good will be high.

The property of having lots of good certificates will allow us to develop efficient probabilistic algorithms, such as the one given above, for other decision problems. We use induction on n. N This is true because a1 is chosen independently of a2 ,. Hence f , as a polynomial in x1 , has degree t and so has at most t roots. Putting this together we obtain Pr[ f a1 ,. One could argue that being right half of the time is not much good, but we can simply repeat the procedure as follows.

Such a procedure, known as a probabilistic algorithm, is clearly extremely useful. Note that it is also efficient assuming that we have a source of randomness and that evaluating the polynomial at a1 ,. Such a procedure is known as a probabilistic polynomial time algorithm. One obvious problem with such a probabilistic algorithm is that it requires randomness. In previous chapters we considered the computational resources of time and space. We measure this by the number of random bits used during its computation.

We will assume perhaps rather unrealistically that we have a source of independent random bits, such as the outcomes of a series of independent tosses of a fair coin. In many probabilistic algorithms we will require more than simple random bits. For instance, in our previous example we needed to choose integers uniformly at random from an interval. In our next example we consider one possible way of doing this using random bits.

We assume that we are given an infinite sequence of independent random bits. We were careful not to insist that such an algorithm must be deterministic. To clarify this we now take the following view.

In order to give a formal definition of a probabilistic polynomial time algorithm we introduce a new type of Turing machine. A probabilistic Turing machine or PTM is a DTM with an extra tape, called the coin-tossing tape, which contains an infinite sequence of uniformly distributed independent random bits.

This tape has a read-only head called the coin-tossing head. The machine performs computations similarly to a DTM except that the coin-tossing head can read a bit from the coin-tossing tape in a single step. The transition function now depends not only on the current state and the symbol in the current square of the ordinary tape, but also on the random bit in the square currently scanned by the coin-tossing head. Note that since the coin-tossing tape is infinite in only one direction the coin-tossing head is not allowed to move off the end of the tape. Indeed, whether a PTM halts on a particular input is itself a random variable.

So by definition any PTM with polynomial running time is halting. We will sometimes consider PTMs that may not be halting. We can now define the complexity class of languages decidable in randomised polynomial time or RP. Moreover if the input is the zero polynomial then the algorithm always rejects and so condition ii above is satisfied.

Also, using Theorem 4. Hence condition i above is also satisfied. The only question remaining is whether the algorithm runs in polynomial time. We introduce a restricted version of this language for which this is certainly true. The input size in this case is clearly O n 2 and the degree of the polynomial is O n. Hence we have the following result. Our next result shows that by repeating the computation polynomially many times we can reduce the probability of an error significantly.

Probabilistic algorithms are still by far the most practical way to test for primality. This can be seen as two distinct problems. First, choosing a large integer at random and, second, testing whether or not the chosen integer is prime. Given a source of randomness it is straightforward to choose a random integer with exactly k bits.

Thus we will concentrate on the latter problem. So far we have only seen an extremely naive exponential time deterministic algorithm for primality testing which is essentially useless Algorithm 2. A major breakthrough in primality testing was the discovery of efficient probabilistic algorithms 4.

Complexity and Cryptography: An Introduction by John Talbot

One of these is the Miller—Rabin algorithm which we present below. Since we have also had available the striking fact that there exists a deterministic polynomial time algorithm due to Agrawal, Kagal and Saxena. However, currently this still has running time O log6 n and so for practical purposes the Miller—Rabin algorithm is more useful.

The proof of this relies on the following lemma. If either of the following two conditions hold then n is composite: Hence if i holds then n is composite. If ii holds then let b be the last integer in the sequence a m , a 2m ,. Many composite integers have lots of Fermat witnesses. Unfortunately there exist some which have very few. The following result tells us that if we could ignore Carmichael numbers then primality testing would be extremely simple.

For details of the basic group theory we will require, see Appendix 3. While if the input is composite, but not a Carmichael number, then Proposition 4. Since this algorithm is also clearly polynomial time we would have a very simple primality testing algorithm if Carmichael numbers did not exist. Unfortunately they not only exist, there are infinitely many such numbers as the following theorem, due to Alford, Granville and Pomerance , implies. Despite this fact some implementations of cryptosystems which require random primes actually use Algorithm 4.

The justification for this being that since there are far more primes than Carmichael numbers of a given size we would be incredibly unlucky to choose a Carmichael number by mistake. We wish to take a more rigorous approach and so require an algorithm which can also recognise Carmichael numbers. The Miller—Rabin primality test makes use of both Fermat and Miller witnesses.

The Miller—Rabin test is clearly a probabilistic polynomial time algorithm since it involves basic operations such as multiplication, calculation of greatest common divisors and exponentiation mod n all of which can be performed in polynomial time. To see that i holds suppose the input n is prime. But by Lemma 4. It remains to prove ii. We consider two cases. Case 1 The input n is composite but not a Carmichael number. However, by Proposition 4. We consider two sub-cases depending on whether or not n is a prime power. Case 2a The input n is not a prime power.

No Carmichael number is a prime power see Exercise 4. Hence the proof is complete. When we introduced PTMs we defined the notion of time complexity only for machines that halt on all inputs regardless of the random bits on the cointossing tape. Simply fix any particular sequence of random bits of the correct polynomial length and use these to decide any input. However, if we do not insist that our PTM is halting then we can still consider algorithms whose expected running times are polynomial and which have zero error probability. Such algorithms are known as Las-Vegas algorithms and can be extremely useful, particularly in situations where it is essential that the answer is correct.

Indeed this class may well turn out to be empty, although proving this would be a major new result. Thus we will consider algorithms which have a reasonable chance of accepting an input from the language, while also having a reasonable chance of rejecting an input not from the language. We simply let M read a single random bit and accept x iff this is 1.

Equivalently toss a coin and accept x iff the coin lands on heads. Such an algorithm is obviously useless, however, if we could make the chance of accepting a correct input significantly higher and the chance of accepting an incorrect input significantly lower this would be useful. This leads to the 82 4 Probabilistic computation class of languages decidable in bounded-error probabilistic polynomial time or BPP.

That is if N accepts more times than it rejects then M accepts, otherwise M rejects. Hence M needs to simulate N polynomially many times and, since N had polynomial running time, so M also has polynomial running time and the result holds. We have the following obvious containments between complexity classes that follow directly from the definitions, Theorem 4. With our new plethora of complexity classes comes a whole range of open questions. Moreover it could do this in time O n in the following way. Once it has read the whole input its transition function can tell it whether to accept or reject depending on whether x belongs to L.

If we wish to use different machines for different input lengths we need to place restrictions on the size of the machines, so first we need a definition of the size of a Turing machine. The size of a Turing machine is the amount of space required to describe it. The obvious restriction to place on a machine if it is to decide inputs of length n from a language L in an efficient manner is to insist that its size and running time are polynomially bounded.

Formally we say that a language L is decidable in non-uniform polynomial time if there is an infinite sequence of DTMs M1 , M2 ,. It is easy to check that the following result holds. We can now show how powerful this new deterministic complexity class really is. This allows us to build a deterministic Turing machine to decide inputs of length n, with polynomial size and running time.

Now, by Proposition 4. This machine clearly decides all inputs of length n correctly and has polynomial size and running time. We list the 4 elements of B1 in Figure 4. We simply consider each satisfying truth assignment in turn. Then f x1 ,. But is this a minimal set with this property? These are both minimal sets with this property. We call such a set a basis for Bn. In fact there is a smaller basis for Bn. A gate computes its output by reading the inputs from its in-edges and applying the Boolean function with which it is labelled to these inputs. It then sends the resulting value along all its out-edges.

The size of a circuit C is the number of gates it contains that is the number of vertices in the underlying graph excluding the input and output vertices , we denote this by C. The depth of a circuit C, denoted by d C , is the length of a longest directed path through the gates that is the length of a longest directed path in the underlying graph from an input vertex to the output vertex.

So the example in Figure 4. Circuits can be used to decide languages in the following way. It is less obvious that the converse also holds. The outputs describe the new state, new symbol and whether the head should move left or right. We will have T n layers in our circuit, one for each possible time during the computation.

Let Bi,t be the component circuit corresponding to square i on layer t. The component Bi,t takes three types of input. If the read—write head is scanning square i at time t then by using the single bits corresponding to the head movement the circuit knows which of these is in fact the current state of M.

The computation of Bi,t depends firstly on the single bits telling it whether or not the read—write head is currently scanning square i. Part of the circuit is depicted in Figure 4. The final layer simply checks which square the read-write head is scanning and reads off the final state of M. Clearly this circuit will decide L on inputs of length n assuming that x is encoded as binary and given to the first layer together with the starting state of M and starting head position.

This follows from the proof of Theorem 4. A probabilistic circuit is an ordinary circuit with some extra inputs y1. We say that a probabilistic circuit C computes a function f: It is not too difficult to see that Theorem 4. The analysis of this is identical to the proof of Proposition 4.

This new circuit clearly has size O n C. By the same argument as that used in the proof of Theorem 4. Fixing this random sequence we obtain a deterministic circuit which computes f x1 ,. Bn n Note firstly that the number of Boolean functions on n variables is The result will follow from simply counting the number of circuits with n inputs and of size s, which we denote by C n, s. Unfortunately the largest known lower bound for the circuit complexity of a problem in NP is in fact linear.

• Vocationalisation of Secondary Education Revisited: 1 (Technical and Vocational Education and Traini
• Energy Resources: Occurrence, Production, Conversion, Use
• Get Started in Windows 7: An absolute beginners guide to the Windows 7 operating system (Teach Yours
• Noformus - Im Bann des Bösen (German Edition)
• Counternarratives: Studies of Teacher Education and Becoming and Being a Teacher (SUNY series, Teach
• The History Of Retrievers (A Vintage Dog Books Breed Classic - Labrador - Flat-Coated Retriever - Go
• Levinas, Judaism, and the Feminine: The Silent Footsteps of Rebecca (Indiana Series in the Philosoph