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).