CMPT 710/407 - Complexity Theory Lecture 1: Introduction
Valentine Kabanets · 2007
Problem 1 was solved by Eratosthenes (via his “Sieve”): Write down all integers less than or equal to N . Then cross out all even numbers, all multiples of 3, of 5, and so on, for each prime less than √ N . If N remains on the list, then N is prime. Problem 2 was solved by Euclid via what is now known as Euclid’s Algorithm for finding GCD of M and N : Initially set r0 = M , r1 = N , and i = 1. While ri 6= 0, assign ri+1 = ri−1remri and i = i + 1. Return ri−1. The important difference between the two algorithms is that Euclid’s algorithm is very efficient (polynomial-time in the sizes of its inputs), whereas Eratosthenes’ algorithm is extremely inefficient. Many other problems in mathematics had/still have inefficient algorithmic solutions (factoring numbers, factoring polynomials, etc.)