1.  Review

• NP = easy to check ``yes''
• coNP = easy to check ``no''
• NP-hard = can reduce all of NP to this problem
• coNP-hard = can reduce all of coNP to this
• NP-complete = NP and NP-hard
• CoNP-complete = CoNP and CoNP hard

2.  3-colorability º _m^p\protect Planar 3-colorability

2.1  3-colorability £ _m^p\protect planar 3-colorability

There is a 13 node graph (``widget'') s.t. the 4 extreme points are constrained so that each pair of opposite corner points must be the same color. Whenever there is a crossing of lines in a planar drawing, insert one of these widgets.

2.2  3-colorability ³ ^p_m\protect planar 3-colorability

obvious.

3.  Some problems

3.1  knapsack

• S = a set of objects
• w(a) = weight of a Î S
• b(a) = benefit of a Î S

The knapsack problem is:

Phrased as a decision problem this is 'Is there a set S¢ where B ³ k '?

3.2  subset sum

Given a set of integers S is there a subset of S¢ such that å_{a Î S¢}w(a) = B .

3.3  Partition

Given a set of integers S is there a partition into 2 sets with equal sum?

3.4  Bin packing

Can this list be partitioned into k bins such that each bin sums to £ B .

4.  partition º _m^p\protect subset sum

4.1  partition £ ^p_m\protect subset sum

let M = å_{s Î S}s . Then let B = ^M/₂

4.2  partition ³ _m^p\protect subset sum

Add the numbers

• N-B
• N-(M-B)

For N large. Each of these 2 numbers will be in different partitions and one of these partitions (minus N-B ) is of the right size.

5.  partition £ _m^p\protect bin packing

Just do 2 bin packing.

6.  Linear programming

At one time people didn't think that linear programming was polynomial.

6.1  the problem

pick {x_i} to maximize å_ic_ix_i subject to "jå_ia_ijx_j £ b_j .

6.2  integer programming

Is there a choice of {x_i} that satisfies the inequalities with integers?

This problem is np complete

6.3  subset sum £ _m^p\protect integer programming

Put in the constraints:

• å_ia_ix_i £ B
• -å_ia_ix_i £ -B

which implies: å_ia_ix_i = B .

Also require: "i 0 £ x_i £ 1 to reduce subset sum to integer programming.

7.  Hamiltonian circuit

Does this graph have a path going through every node exactly once and returning to the start?

7.1  vertex cover £ _m^p\protect hamiltonian circuit

There is a 4 node directed 'widget' with 2 inputs and 2 outputs s.t. a hamiltonian path can enter through either (or both) input(s) and hit all nodes on a hamiltonian circuit.

A similar widget exists for the undirected case.

Then, you use these widgets in a way which I can't easily describe. For every node in the original graph a loop is created.

8.  Travelling salesman problem

Is there a hamiltonian circuit such that:

Is there a hamiltonian circuit such that total cost £ k ?

8.1  hamiltonian circuit £ _m^p\protect TSP

Put weight one on all of the nodes then ask if there is a TSP with k = #nodes .

9.  Minimum node deletion bipartite subgraph

Given a graph G, can I make it bipartite by only deleting k nodes?

Can clique £ _m^p MNDBS?

reduction: Take the original graph, and complement it. Add the number of nodes again, fully interconnecting a new node to the complemented graph. Is this a reduction?

10.  New complexity classes

• NC = problems that are parallelizable = solvable in polylog time = log(n)^O(1) with a polynomial # of processors.

Does P = NC? Probably not. Example: Does program A finish in time n?

The example is in P-complete.

• BPP = in polytime probably(with high probability) correct. (Bounded error probabilistic problem)
• BQP = same as BPP on a quantum computer.