SUNY Geneseo Department of Computer Science

Open Problems Concerning Lower Bounds

{Date}

CSci 141, Spring 2005
Prof. Doug Baldwin

Return to List of Lectures

Previous Lecture

Misc

Hand out Lab 14

End-of-semester stuff

SOFI's next Monday (May 2)
- Need czar/czaritza (Drew)
Final
- Monday, May 9, 8:00 AM
- Comprehensive but biased towards trees, limits
- Similar rules and format to hour exams
- 3 hours, designed for 2
- Donuts and cider

Questions?

Open Problems re Optimality

Section 16.3

Questions about lower bounds often "open"
Problem is tractable vs intractable
Factoring
- Something done to intractable problems?
Optimization problems
NP problems - are they really intractable?

What does this all mean to you?

Internet commerce & cryptography
- All depends on factoring integers
Can you give your copy of Internet Explorer to your friend in France?
- Copyright issues
- Export of encryption technology
  - Strength of encryption, i.e., length of integers that have to be factored
What if P = NP?
- NP = non-deterministic polynomial time
- Pragmatically: lots of problems that are intractable on our computers
- Non-deterministic algorithm for factoring
  - i.e., factor( n ) returns <x,y> such that x*y = n
- Non-determinism is....
  - Processing all possibilities at once

        factor( n )
            for all possible x's between 2 and n/2 (simultaneously)
                if x divides n
                    return < x, n/x >

So someone discovering that P = NP would be a "non-constructive" proof that factoring is fast
- ...Which would be bad for people who rely on current public-key cryptography, except they wouldn't know how long it would be before someone found the fast factoring algorithm.

Non-deterministic computers?

Parallel computers - constant number of processors
DNA computing - "just" parallel computing?
Quantum computing

Even harder problems

Read sections 17.1 and 17.2

Next Lecture