NP-complete solution given is exponential

[aleph1 () DFW NET (Aleph One)]

---------- Forwarded message ----------
Date: 19 Sep 1997 13:07:48 -0600
From: Chris Hall <hallc () dimensional com>
Newsgroups: sci.crypt, sci.math
Subject: NP-complete solution given is exponential

Claim: There is no known polynomial-time algorithm for solving an
    NP-complete problem.

Proof: Before today (19 Sep 1997) none were known of in the open community.
    One person posted a claimed solution, but I will demonstrate that this
    program still runs in exponential time.

    I have written a simple program which demonstrates that John's program
    takes exponential time.  It produces expressions of the form

    !(!(!....(!a^!b)^c)^!d)^e)^!f)....

    Notice the pattern of variables 3+, it alternates between negating the
    variable and not.  The basic principle is that each level of nesting
    should match on roughly half the set of possible assignments and the
    negation that appears at the left forces the program to negate such a
    set.  That is, I tried to get the program to negate exponentially sized
    sets (and succeeded).

    Here is the source code:

------------------------------

#include <stdio.h>

int
main(int argc, char **argv)
{
    short   i, num_args;

    if (argc != 2) {
        fprintf(stderr, "invalid arguments.\n");
        return -1;
    }

    num_args = atoi(argv[1]);
    if (num_args < 2) {
        fprintf(stderr, "invalid num_args\n");
        return -1;
    }

    printf("(");
    for (i = 0; i < num_args-2; i++)
        printf("!(");
    printf("!0^!1)");
    for (i = 2; i < num_args; i++) {
        printf("^");
        if (i % 2 == 1)
            printf("!");
        printf("%d)", i);
    }
    printf("\n");

    return 0;
}

------------------------------

    The following is a table demonstrating the results of running John's
    program against the input produced by mine.  The first column gives the
    number of variables in the resulting expression, the second column
    gives the length of the expression in characters, and the third column
    gives the amount of user-space time as reported by the time command
    (I'm running Linux).

     i | len |  time
    ---+-----+--------
     8 |  41 |  0.030u
     9 |  46 |  0.030u
    10 |  52 |  0.020u
    11 |  58 |  0.050u
    12 |  65 |  0.070u
    13 |  71 |  0.120u = 1.7  * previous
    14 |  78 |  0.160u = 1.3  * previous
    15 |  84 |  0.290u = 1.8  * previous
    16 |  91 |  0.460u = 1.6  * previous
    17 |  97 |  0.780u = 1.7  * previous
    18 | 104 |  1.300u = 1.67 * previous
    19 | 110 |  2.020u = 1.55 * previous
    20 | 117 |  3.470u = 1.72 * previous
    21 | 123 |  5.410u = 1.56 * previous
    22 | 130 |  8.960u = 1.66 * previous
    23 | 136 | 14.100u = 1.57 * previous
    24 | 143 | 23.030u = 1.63 * previous

    Note how the time increases exponentially (the average of the last
    seven deltas is 1.62) in the number of variables (lower exponent in
    the size of the input, but still exponential).

    Anyone is free to use my code to verify my claim, but I'm fairly
    certain about the results: there is no known polynomial-time algorithm
    for solving an NP-complete problem.  Q.E.D.

                                                                Cheers,
                                                                Chris Hall

P.S. Please reply to hall () counterpane com as that is my normal e-mail
     at Counterpane Systems (work, and where I prefer to receive e-mail).