PUMaC 2016 · 加试 · 第 2 题

Problem 2.8. (5 points) (a) (3 points) Explain why the algorithm described above, that finds 1 + 2 + · · · + n by adding up the numbers, is not a polynomial-time algorithm by Definition 2.3.1. (b) (2 points) Describe, in words, an algorithm that finds 1 + 2 + · · · + n in polynomial time. (Hint: the algorithm is quite simple; don’t overthink it!) Polynomial-time algorithms are important because they are fast compared to algorithms that do not take polynomial time. For this reason, some of the most important problems in computer science center around which algorithms run in polynomial time and which do not. As we will discuss later in the power round, this concept is crucial for cryptography: the idea behind cryptography is that you want to encrypt things quickly (the encryption algorithm should take polynomial time), but decryption (the algorithm that determines the original message from the encrypted message) should have to be slow (not be a polynomial-time algorithm). An example of a process that is thought to not be possible in polynomial time (though this is a hotly debated question among computer scientists) is that of factoring a positive integer n . There is no known algorithm that factors n in polynomial time in the length of n , and many computer scientists believe that such an algorithm does not exist. This is the basis of many encryption schemes, some of which you will be introduced to later. In general, when people speak of polynomial-time algorithms, they mean deterministic polynomial- time algorithms, i.e. algorithms that do not make use of randomness and thus give the same output. However, sometimes it is useful to generalize the concept of polynomial-time algorithms to include probabilistic algorithms, i.e. ones that make use of randomness. Definition 2.3.2. A probabilistic polynomial-time algorithm (henceforth PPT algorithm ) is a gen- eralization of the concept of polynomial-time algorithms that includes non-deterministic algorithms. For example, an algorithm that takes an integer n as input, randomly chooses two integers 4 between 1 and n , and outputs their sum is a PPT algorithm. The algorithm that takes an integer n as input and outputs 2 n is also a PPT algorithm: PPT algorithms aren’t required to use randomness, so all polynomial-time algorithms are considered PPT algorithms. 3 Specifically, this algorithm takes time O ( n lg n ). This is because adding a number with b bits takes b operations, on average the numbers from 1 to n have roughly lg( n ) bits, and there are n numbers to be added. However, the precise complexity is not important for the purposes of this power round. 4 Unless of course such an algorithm is implemented really inefficiently. PUMaC 2016 Power Round Page 7 3 Some Probability Theory Starting with Section 5, we’ll be working with probabilities and PPT algorithms a lot. This section will introduce some of the concepts you’ll need. Recall that Pr [event] denotes the probability of an event. 3.1 Probabilities Over Different Spaces I rolled a fair six-sided die and looked at the result. Then I rolled another fair six-sided die and didn’t look at the result. What is the probability that the sum of the rolls is 9? And the answer is... well, it depends on whom you ask. Some people will tell you that the probability is either 0 or 1: either the sum is 9 or it isn’t. But let’s leave this view aside, since it doesn’t tell us anything interesting. 1 Another possible answer to the question is . This is because out of the 36 possible pairs of 9 rolls, four of them ((3 , 6), (4 , 5), (5 , 4), and (6 , 3)) give a sum of 9. This makes sense from your perspective, and from the perspective of anyone who hasn’t seen the first die. Based only on the information you have, there’s a one-in-nine chance that the sum of the two dice is 9. A third possible answer is that it depends on the first die’s roll. If the first roll was 1 or 2 then 1 the probability is 0, and if it was 3, 4, 5, or 6 then the probability is . And indeed, if you asked 6 1 me what the probability that the sum is 9 is, I would tell you either 0 or (depending on what I 6 observed on the first die). The distinction here is a matter of probabilities over different spaces: in the former case, the probability is taken over the space of all possible pairs of die rolls; in the latter case, the probability is taken over the space of all possible rolls of the second die, with the roll of the first die already known.