A computaional problem is said to be in the class P
of polynomial time problems whenever there's
an algorithm which can find a valid solution in
a number of elementary steps which is always less than a certain polynomial function
of the size of the input data (one rough measure of this
size could be the number of digits used in a reasonnably thrift encoding of
the input data).
The class NP (nondeterministic polynomial time problems)
consists of those problems which could be so solved nondeterministically,
which is a fancy way to say that an unlimited number of lucky guesses are allowed
in the process which arrives at a solution.
Such a nondeterministic process must still be such that only valid solutions
are produced...
To put it in simpler words, a problem is in NP if and only if a solution of
it can be checked in polynomial time
(an explicit nondeterministic algorithm would then be to guess a correct solution
and check it).
Karp discovered that there are problems in NP which he dubbed "NP-complete"
because they are at least as tough to solve as any other problem in NP, in the
following sense:
Any NP problem can be reduced in polynomial time by a deterministic algorithm
to the solution of an NP-complete problem whose data size is no more than
a polynomial function of the original input data.
Therefore, if any NP-complete problem could be solved deterministically
in polynomial time (i.e., if it was a P problem) then all NP problems
would be in P and we would thus have P = NP.
Karp's original NP-complete problem (dubbed SAT)
was the satisfiability of boolean expressions:
Is there a way to satisfy a given
boolean expression (i.e., make it "true") by assigning true/false values
to the variables in it?
The SAT problem is clearly in NP (just guess
a correct set of values and compute the boolean
expression to make sure it's true).
Karp proved from scratch that any problem in NP can be reduced in polynomial
time to a commensurable boolean satisfiability problem, thus establishing
SAT to be NP-complete.
If a known NP-complete problem like SAT can be reduced polynomially to some NP problem Q,
the problem Q is then established to be NP-complete.
This way, from Karp's original NP-complete problem,
the list of known NP-complete problems has grown to include
literally hundreds of "classical" examples.
The tantalizing thing is that many such NP-complete problems are very practical
problems which, at first, look like they could be solved in polynomial time.
Yet, nobody has ever "cracked" one of these in polynomial time
or proved that such a thing could not be done...
Therefore we still don't know whether P=NP or not.
The problem is named after the German mathematician
Lothar
Collatz (1910-1990) who formulated the conjecture in 1937.
The sequence
A087003,
may be defined as the Dirichlet inverse of the
character modulo 2.
It was first defined by Labos E.
as the sum of all the Möbius values found at the points of the Collatz trajectory
until a "4" is found (2003-10-02).
However, Marc Lebrun (2004-02-19) has shown that either definition simply
means that A087003 is equal to the Möbius function
at odd points and vanishes at even points...
All told, the Collatz sequence itself turns out to be irrelevant !
