American            British
10^6   million             million
10^9   billion             milliard (or thousand million)
10^12  trillion            billion
10^15  quadrillion         thousand billion
10^18  quintillion         trillion

Counting is in Latin.

10^99 duotrigintillion
10^100 ten duotrigintillion = 1 googol

10^303 centillion

NP-Completeness

a) the problem is in NP
b) every problem in NP is polynomial-time reducible to the given problem.  ALTERNATIVELY, a known NP-complete problem is polynomial-time reducible to the given problem.

Meaning you can translate the input from the first problem to the second in polynomial time so that each problem yields the same result as each other.

HAMILTONIAN CYCLE
CLIQUE
PARTITION

Let's take a look at the TRAVELING SALESMAN problem.

We have a list of cities and a list of distances between all pairs of cities.  We also have a number m.  QUESTION:  is it possible to travel between cities, visiting each city exactly once, returning to the initial city, so that the total distance traveled is <= m?

Is this problem NP-Complete?

HAMILTONIAN CYCLE:  Given a graph G=(V,E) is there a cycle through the graph that contains every vertex exactly once?

We need to reduce HAMILTONIAN CYCLE to TRAVELING SALESMAN.  The reduction always goes from the KNOWN NP-Complete problem to the one you are trying to prove.

So we must construct a polynomial-time reduction from HAMILTONIAN CYCLE to TRAVELING SALESMAN.  This means we have come up with an algorithm that transforms the input from HAMILTONIAN CYCLE to a valid input for TRAVELING SALESMAN (that preserves the answer).

HAMILTONIAN CYCLE:  The input is a graph.  A set of vertices and edges.
TRAVELING SALESMAN:  The input is a list of cities, of distances between pairs of cities, and a number m.

So, Make the list of cities the vertices of the graph.
For each edge in the graph, set the distance between corresponding cities to be 1.
For each pair of vertices not connected by an edge in the graph, set the distance between the corresponding cities to be v+1, where v is the number of vertices in the graph.
Set the m to be v.

PROOF.  YES==>YES and YES <== YES

You could do YES==>YES  and NO ==> NO

You cannot do YES==>YES and NO <== NO (This is proving YES==>YES twice.)

Let's say HAMILTONIAN CYCLE gives us a YES.  That means there is a path hitting every node exactly once.  The corresponding path in TRAVELING SALESMAN will visit the same cities and since there is an edge between cities in the original problem, the distances in TRAVELING SALESMAN will all be 1.  This means that the total distance will be v and v <= m (since v = m), so TRAVELING SALESMAN also gives us a YES.

Now, let's say TRAVELING SALESMAN gives us a yes.  This means that there is a way to do to visit all v cities with a total distance <= v.  Since the total distance is <= v, then our path must not contain any of those v+1 edges.  So, we're only traveling between cities whose distance is 1 from each other.  So these paths correspond to edges in the HAMILTONIAN CYCLE.  Thus, we can visit every point in G along edges that exist, exactly once, returning to our starting point, so HAMILTONIAN CYCLE is also YES.

We still need to prove that TRAVELING SALESMAN is in NP.  You have each thread in a nondeterministic machine travel a different cycle, computing the total distance traveled.  If there is a path of distance <= m, return YES.

Now, notice that our reduction from HAM to TSP, considers all possible inputs for HAM, but does not actually generate all possible instances of TSP.  This is perfectly legal.  This is how functions work.  They have to work all possible inputs, but there's no law that says that all possible outputs have to be derived.

This technique is called "RESTRICTION".  And this is the simplest NP-completeness proof.  The harder ones are called "LOCAL REPLACEMENT" and "COMPONENT DESIGN."  The last one is especially hard and is used when there is no obvious connection between the two problems.

So, let's begin with "how are these problems different?"