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