CSC301.01 2015F, Class 40: Looking Ahead: P vs. NP

Overview

Preliminaries

Exam 2 due Friday.
Final exam next Tuesday at 2pm (in this room).
- One 8.5x11 inch or A4 page of notes, hand-written on both sides.
- Simpler version of take-home exams.

For the last problem, what should I choose when I have multiple trees with the same frequency?

The shorter tree.

For the last problem, do I need to include characters with a frequency of zero?

Yes.

For the class rating problem, aren't a and c the same problem?

I believe that a may require n steps (since there may be at least n 0's) but c should be doable in O(logn).

Do you have an example of the task completion done yet?

Not yet.

Is the "max-flow with shortest path" approach correct?

Yes.

Will you bring random numbers to class on Wednesday?

Yes.

Design an algorithm that finds out whether a weighted graph contains an acyclic path of length l. (Alternately, that finds the path.)

Ideas

We are confident that exhaustive search will work

Most people are happy when they have an O(nlogn) algorithm.
- Google doesn't like those. They want O(n)
Sometimes we make do with O(n^3) (e.g., Floyd-Warshall). It's still much better than n!
What do you do when you come up with an inefficient algorithm?
- We can do better! Try something else.
- Google it
- Ask other people
What happens when you still fail to do better.
- Prove that you can't do better. (We did that for sorting.)
- Try using randomness and accept an approximate answer.
- Solve something similar and easier.
- Cry.
Computer scientists encountered a lot of problems for which they had not proof of minimum time as exponential/factorial, but also no non-exponential/factorial solution.

We classify problems as a way to get a handle on these issues.
P - the set of problems for which we know a polynomial time algorithm. (Almost every algorithm we've done in this class.
NP - the set of problems for which we can verify the solution in polynomial time.
P is a subset of NP.
Is P a proper subset of NP?
- Most computer scientists think so.
- Donald Knuth does not (at least the last time I checked).
If P = NP, encryption fails.
- Most encryption relies on factoring.
- Factoring is in NP, but not known to be in P.

We have a set of problems that are known to be as hard as any other problem in NP. These are the "NP complete" problems"
If you can solve any of these problems in polynomial time, you can solve any problem in NP in polynomial time.
The NP complete problems are problems that we can reduce other problems to quickly.
- An example in P: We saw that if we could do max-flow quickly, we could solve bipartite matching quickly.
We tend to use transitivity to see that things are NP-complete.

Given a weighted, non-directed graph, find the shortest path that visits every node.
Given a weighted, non-directed graph, find whether there is a path less than a certain weight that visits every node.
Is this a useful problem?
- Truck companies that need to get deliveries to multiple cities.
- Lots of problems have a requirement that you find the most cost-effective way to visit a group of locations.
What do we do, given that we can't solve it efficiently?
We look for an approximation. (Skiena gives us one that is no worse than twice as long as the best path.)

Given a Boolean formula of N variables with just and, or, and not. Is there an assignment of truth values to the variables for which the formula holds?
We don't know anything significantly better than "try every assignment"
SAT is key to NP-completeness. There's a proof that every problem in NP reduces to SAT. (So if you get 2400, you are golden.)