SUNY Geneseo Department of Computer Science

Intractability and Factoring

{Date}

CSci 141, Fall 2003
Prof. Doug Baldwin

Misc

End-of-Semester

Last class we realized that the number of times the best Towers of Hanoi solver moves a disk is

Which we asserted has closed form B(n) >= 2ⁿ - 1

Mini-assignment: prove that this is the correct closed form for the recurrence

Proof by induction on n
Base case, n = 1
- B(n) >= 1 [from recurrence]
- >= 2¹ - 1 [from closed form]
- = 2 - 1
- = 1
Induction hypothesis: assume k-1 is natural number and B(k-1) >= 2^k-1 - 1
Show B(k) >= 2^k - 1
- B(k) >= 1 + 2B(k-1) [from recurrence]
- >= 1 + 2( 2^k-1 - 1 ) [induction hypothesis]
- >= 1 + 2^k - 2
- >= 2^k - 1

Read Section 16.3 (open problems)

Open problem = any as-yet unsolved problem
- e.g., lower bound not known yet
Tractable vs intractable problems
- Tractable = easy to solve, polynomial time
- Intractable = hard to solve, e.g., exponential
Incomprehensible stuff

Factoring

Given a natural number, n, find 2 other smaller naturals a, b, such that n = a*b

Factoring is solvable

    factor(n)
        for i = 2 to n-1
            if n / i is a whole number
                return < i, n/i >

Worst case: n-2 iterations of loop

But n isn't the right measure of problem size

See thawte.com re SSL security, cryptography contests