Bugtraq mailing list archives
Re: NP-completeness algorithm: errata
From: aleph1 () DFW NET (Aleph One)
Date: Thu, 2 Oct 1997 17:37:16 -0500
From Hoey () AIC NRL Navy Mil (Dan Hoey)
Organization Navy Center for Artificial Intelligence Date 19 Sep 1997 22:39:43 -0400 Newsgroups sci.math,sci.math.symbolic,sci.crypt,comp.misc,comp.programming,comp.security.misc,comp.theory Message-ID <199709192239.Hoey () AIC NRL Navy Mil> jhayward () students uiuc edu (jonathan seth hayward) writes:
I now have what I believe to be a polynomial time solution to an NP-complete problem (specifically, satisfying a propositional formula expressed in terms of parentheses, variables, negations, and conjunctions)....
I will post a uuencoded compressed tar....
Posting uuencoded binaries to discussion groups is an abuse of Usenet. You've done this about 14 times now. Please do not do so any more. Posting URL's for your code (as you've done) is a good way of distributing code, and renders posting the targets of those URLs redundant. See news.announce.newusers. Please cancel your own net-abuse, don't wait for Dick Depew. Even if you're not abusive enough for Dick to cancel, it's still abuse. A change to responsible posting would go a long way toward convincing people you're not a crank. Also, posting the same message _separately_ to seven newsgroups is wasteful and potentially abusive. Learn how to crosspost. See news.announce.newusers. This, my response, is crossposted to the seven newsgroups you sent your stuff to. But I've directed the followups to comp.programming, because the programming method you are using does not have mathematical, theoretical, cryptological, or security implications. It's a fairly usual way of program manipulation of Boolean expressions, and does not reduce the complexity of Boolean satisfiability to polynomial time. What you've "discovered" is that any propositional formula on {p,q,r,...} can be written as (p & W) | (~p & X) for formulas W and X that do not mention p. So you take the lowest-numbered variable (in some ordering of variables) mentioned in the formula as "p" in this form, and write W and X in this form (for higher-numbered variables), with particular conventions for representing logical TRUE and FALSE. Sharing equivalent structure is expected. This is not rocket science. Your statement of what complement (logical negation) does is a long way of saying Complement( (p & Y) | (~p & X) ) == (p & Complement(Y)) | (~p & Complement(X)) but that's not a problem. The problem comes when you have intersection (logical conjunction), where (in the case that p is the lowest-numbered variable, we have Intersect( (p & Y) | (~p & Z) , W ) == (p & Intersect(Y,W)) | (~p & Intersect(Z,W)). This may or may not be what you described. Your description got so disorganized with attempts to micro-optimize tautologies and equivalent subexpressions I could not tell. Such optimizations do not significantly affect the algorithm's performance because they are rarely applicable when expressions get to a reasonably large size, unless you can prove otherwise. There were a lot of unproven claims about how this or that was the only possible case, but little or no mention of the usual case, in which Y, Z, and W are all nontrivial expressions with no significant sharable substructures. The problem with Intersect() is that your claim that the output is only O(1) plus the size of the inputs is false. Suppose Y and Z have few nodes and W has many nodes. The result has two large terms Intersect(Y,W) and Intersect(Z,W), each of which may easily be large, like W. So by intersecting a small expression with a large expression we have about doubled the total size of the expression. It's clear we can have O(n) small expressions; if we intersect them in one at a time, doubling the size of the large expression each time, we get an expression of size 2^O(n). You may be tempted to try taking advantage of the associativity of Intersect(), but Complement()ing each step before Intersect()ing breaks that idea. You've mentioned in an "errata" posting a requirement that "variables be indexed in order of appearance;" this sounds like an attempt to prevent Y and Z from having higher-numbered variables than W, in hopes of making Intersect(Y,W) and Intersect(Z,W) share a lot of structure (though if your proof relies on this, you're supposed to say so). But the ordering of variables is globally defined, and the ordering of these variables may have been predetermined by an earlier part of the expression than this Intersect() that's blowing up. If you claim you can force a fortuitous variable ordering or structure-sharing you have to prove it. There could conceivably be some way of manipulating these expressions or reordering variables to make them stay small. But finding that way is what me mean by "proving P=NP". To do that, you will have to stop programming and start reading and writing proofs. Writing code and waving hands about it being polynomial is not going to win friends and influence your professor. It is not enough to fail to be obviously wrong, you must find a way to be obviously right. And remember, posting ever newer versions of broken code in half a dozen newsgroups is just going to convince people you're more interested in publicity than in problem solving. The hard part of proving P=NP is not writing code, and it's not getting your code distributed. It's convincing people you can solve the problem and do it in polynomial time. You can discuss and explain your method in words in comp.programming and maybe learn what is hard about NP, or redirect from there to your favorite group (not groups). Or you can continue your binary spam spree and join the years-long parade of clowns. The choice is yours: what do you want to be? Dan Hoey Hoey () AIC NRL Navy Mil
Current thread:
- Re: NP-completeness algorithm: errata Aleph One (Oct 02)