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

_Overview_

* Preliminaries.
    * Admin.
    * Upcoming Work.
    * Extra Credit.
    * Questions.
* Path length.
* Running times.
* Basic complexity classes.
* NP-Complete problems.
* TSP.
* Satisfiability.

Preliminaries
-------------

### Admin

### Upcoming Work

* 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.

### Extra Credit

* CS Table tomorrow.
* CS Extras Thursday.

### Questions

_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.

Path Length
-----------

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

Ideas

* Use exhaustive search
* A variant of Dijkstra
* Use dynamic programming
* Modified dfs/bfs
* A variant of Floyd-Warshall (all-pairs shortest path)
* Turn it into a max-flow problem

We are confident that exhaustive search will work

* n*(n-1)/2 paths of length 1
* n*(n-1)*(n-2)/? paths of length 2.
* Approximately n! total paths
* That computer in China does about 10^16 floationg point operations per
  second.
* How long will that computer take on a graph of size 50?
* A bit longer than the heat death of the universe.

Running Times
-------------

* 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.

Basic complexity classes
------------------------

* 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.

NP-Complete problems
--------------------

* 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.

TSP
---

* 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.)

Satisfiability (SAT)
--------------------

* 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.)