Re: P = NP!
- From: Joshua Cranmer <Pidgeot18@xxxxxxxxx>
- Date: Sun, 12 Oct 2008 16:06:49 -0400
Cory Knapp wrote:
Based on his description of the algorithm, and some comments he made
on a public math forum (mymathforum.com), it seems his algorithm
amounts to a DFS on a ternary tree*, which traverses the tree until it
finds a contradiction, and then backs up and tries again until it
makes it to a leaf (Or doesn't). Obviously, this is not a polynomial
algorithm. I wrote up a verbose, lengthy, and inelegant (and perhaps
incorrect) proof at the forum previously mentioned.
I strongly suspect that at least three different versions of the "algorithm" exist. At best, he is bad at writing; at worst, he is intentionally misleading and vague.
The format of the paper is as follows (for anyone too lazy to see the link):
1. Introduction. Mention that it's a polynomial time algorithm to solve 3-SAT, an NP-Complete problem.
2. Describe the SAT problem.
2a. First blunder is failing to distinguish between the SAT and CNF-SAT forms of the problem. Misleading in numerous ways, but since SAT has a polynomial-time reduction to 3-SAT, it's somewhat acceptable, although quite unprofessional.
2b. Talks about the DNF form for no reason I can divine. He claims it's for "explanation purposes," but far from being enlightening, it's downright confusing.
3. Describe the Algorithm.
3a. We start by, once again, referring to the DNF form even though we're explicitly told we're not trying to solve the DNF form.
HINT:
____ ___ ____ ___ _____ ___ _ _ _____ _
| _ \ |_ _|| _ \ |_ _||_ _| / _ \ | | | ||_ _|| |
| |_) | | | | |_) | | | | | | | | || | | | | | | |
| _ < | | | __/ | | | | | |_| || |_| | | | |_|
|_| \_\|___||_| |___| |_| \___/ \___/ |_| (_)
3b. Define tc(vx, x), which appears to be equivalent to "true iff x is satisfiable if vx is true". Strongly reminiscent of <http://www.sciencecartoonsplus.com/images/miracle3.gif>.
3c. Oh, by the way, the algorithm is essentially "for all tokens [appearances of a or ~a] in the expression, if one tc(token, x) is true, then it's satisfiable."
4. Defining the implementation of the magic function above.
4a. Hey, we're back in CNF after two pages of DNF. No clear distinction that we've changed forms, except for a more-or-less in-passing mention and the sudden realization that the algorithm is not describing DNF anymore.
Quite frankly, no matter that we've had at least four warnings that DNF is only for instructional purposes, all they do is make everything even muddier. It's certainly not making this magic tc function any easier to understand, especially because we now have an description working in a different form from the definition of the problem.
4b. The first paragraph of the algorithm is easy enough to understand: go through the clauses from left to right, checking to see if each clause has a valid token. If a clause doesn't have one, the function returns false.
4c. The second paragraph starts simple (a valid token is one that doesn't contradict any earlier assumed value). The second part of the paragraph is just confusing referencing the "TR definition", a phrase not mentioned anywhere else.
4d. In short, here's some pseudocode (quite python-like):
function validToken(clause, knownTokens):
for each token in clause:
if token.variable in knownTokens:
if token.negated = knownTokens[token.variable].negated:
return TRUE
else:
knownTokens[token.variable] := token
return TRUE
return FALSE
function isSatisfiable(x):
tokens := {}
for each clause in x:
for each token in clause:
if token not in variables:
tokens.push(token)
while tokens is not empty:
token := tokens.pop()
knownTokens := {token.variable => token.negated}
for each clause in x:
if not validToken(clause, knownTokens):
continue outer loop
return TRUE
return FALSE
DISCLAIMER: I am basing this off of the description of the algorithm on pages 3 and 4. A close reading will note that this is an important distinction.
5. Claim of running time.
5a. Did you notice that the algorithm is described with not even an attempt at proof of correctness? It seems to consist of a "It feels right" aura.
5b. Did you also notice a lack of backtracking? That's why it's polynomial. It's also why it's incorrect, since SAT is a problem where "local optima don't correspond to global optima" (to quote a cljp poster, originally made in reference to another NP-complete problem).
6. Code in C#.
6a. Not in pseudocode.
6b. C# is a language that's far from cross-platform, making it inaccessible to those like myself who operate Linux...
6c. ... not to mention that it's badly written code. For example, naming a variable `Not,' which is practically guaranteed to make you have to read the code three times to be sure it's doing the right thing.
6d. It's also badly formatted, with line breaks inconveniently in the middle of functions or (even worse) in the middle of an expression. The syntax highlighter's choice of colors is also an eye-hurting one.
6e. Finally, it doesn't appear to match the pseudocode I generated from my best understanding of the algorithm, in that it fails to reset the knownTokens part.
7. A final words section, i.e. "This is a big, important question and I solved it." Difficult to say whether that `I' is an *I* or merely an I, though.
.
- Follow-Ups:
- Re: P = NP!
- From: Tim Smith
- Re: P = NP!
- References:
- P = NP!
- From: Yaakov Davis
- Re: P = NP!
- From: Jan Andres
- Re: P = NP!
- From: Cory Knapp
- P = NP!
- Prev by Date: Re: Which axiom prohibits this kind of construction?
- Next by Date: Re: Some of his math... for free!
- Previous by thread: Re: P = NP!
- Next by thread: Re: P = NP!
- Index(es):
Relevant Pages
|
