From: Ken Cox <kcc@research.bell-labs.com>
Subject: Re: NP complete problems
Date: Fri, 06 Apr 2001 18:52:11 -0500
Newsgroups: sci.math
Summary: Is factorial-time the best known result?

Jim Nastos wrote:
>   Just the other day, I was looking on the web for this, and I found a
> reference that said that facotrial time was the best-known... I didn't
> quite believe it. Do you know when this result was proven?

Garey and Johnson do not give a citation for the proof, or
mention when it was first done.

What do you mean by "factorial time was the best-known"?
IIRC, there are NP-complete problems for which the best
known exact algorithm takes factorial time.  By the way,
the time to do a factorial algorithm *is* exponential,
in the NP-complete sense of "exponential", that is,
O(2^p(n)) for some polynomial p.


Take the following problem:  Given a number n, generate
all strings that are permutations of the numbers {1...n}
in binary, where each number uses exactly upper(log(n))
bits (using binary log throughout). For example, n=3, we
want all permutations of 01, 10, 11, which is 011011,
011110, 100111, 101101, 110110, 111001.

The above algorithm is factorial in n, since there are
n! such strings.  Using the technique of G&J, we can show
that it is O(2^p(n)) for some polynomial p as follows:

The length of each string is no more than n*(log(n)+1)
characters.  There are exactly 2^(n*(log(n)+1)) such
binary strings, so if we print all of them we do at least
as much work as the problem.

Printing one string takes n*(log(n)+1) time, so printing
all of them takes n*(log(n)+1)*2^(n*(log(n)+1) time.
Once n gets large enough, n*(log(n)+1) is less than n^2.
Once n gets large enough, n^2*2^(n^2) is less than 2^(n^3).
So solving the above factorial algorithm takes no more
than 2^(n^3) time, once n is large enough; which is to
say, it is O(2^(n^3)).
 
-- 
Ken Cox                  kcc@research.bell-labs.com