[deleted]
The 2-MAXSAT Problem Can Be Solved in Polynomial Time
11–20 of 106 posts
Re: The 2-MAXSAT Problem Can Be Solved in Polynomial Time
#12For me, the following is a bit that seems particularly prone to be invalidated, even more so considering that the author doesn't present any proof of it:
> Here, we notice that if we had one more span, , for example, it would be connected to , but not overlapped with . Being aware of this difference is important since the overlapped spans imply the consecutive ‘’s, just like and , which correspond to two consecutive ‘’s: (c2 , ) and (c3 , ). Therefore, the overlapped spans exhibit some kind of transitivity. That is, if s1 and s2 are two overlapped spans, the s1 ∪ s2 must be a new, but bigger span. Applying this operation to all the spans over a p-path, we will get a ’transitive closure’ of overlapped spans.
Re: The 2-MAXSAT Problem Can Be Solved in Polynomial Time
#13Usually when I see these things, I check if the author seems to have the right background. Yangjun Chen is a full professor at the University of Manitoba, but he doesn't seem to work in computer science theory. It looks like the paper was previously published in a relatively low impact AI conference last year. It seems like it should be in FOCS, STOC, or a prestigious math journal to have significant credibility.
Many of those journals don't take P=NP proofs because they often come from quacks. Also, I wouldn't be surprised to see the start of a full proof coming from a non-theorist. Theorists have failed to make headway on P=NP for decades, so it would be reasonable to assume that some insight from a different place would be required.
Re: The 2-MAXSAT Problem Can Be Solved in Polynomial Time
#14Re: The 2-MAXSAT Problem Can Be Solved in Polynomial Time
#15P=NP alert
I could believe that an O(n^5) algorithm, like what was presented here, can satisfy P==NP, but still maintain the status quo where P!=NP for all practical problems. That is honestly what matters most of the time. Still, there's almost certainly a mistake in this paper.
How so? Impossibly large constants?
Re: The 2-MAXSAT Problem Can Be Solved in Polynomial Time
#16Since the paper claims to give an algorithm for solving an NP-hard problem, e.g. it's a constructive proof, not just an existence proof, then presumably the author should be able to reduce some other problems to this one (2-Maxsat) and solve them as a demonstration.
I'd be more inclined to believe their P=NP claim if they used it to grab all of Satoshi's bitcoins. That should be the first order of business for anyone finding an efficient algorithm for the ECDLP (Elliptic Curve Discrete Log Problem), as implied by their constructive proof.
Re: The 2-MAXSAT Problem Can Be Solved in Polynomial Time
#17For me, the following is a bit that seems particularly prone to be invalidated, even more so considering that the author doesn't present any proof of it: > Here, we notice that if we had one more span, , for example, it would be connected to , but not overlapped with . Being aware of this difference is important since the overlapped spans imply the consecutive ‘ ’s, just like and , which correspond to two consecutive…
If you put a \ in front of your * you can get the * to show up instead of italicizing. *Example*
Re: The 2-MAXSAT Problem Can Be Solved in Polynomial Time
#18P=NP alert
I could believe that an O(n^5) algorithm, like what was presented here, can satisfy P==NP, but still maintain the status quo where P!=NP for all practical problems. That is honestly what matters most of the time. Still, there's almost certainly a mistake in this paper.
Though, P and NP are intrinsically defined asymptotically, so I'm not sure what it means for P != NP for all practical problems, other than saying that something like 80*n^5 is impractical to compute for n=10000, say.
Re: The 2-MAXSAT Problem Can Be Solved in Polynomial Time
#19"Hence, we provide a proof of P = NP."
Now map a big, critical and difficult problem to the 2-Maxsat problem, solve it in polynomial time, get rich and come back to argue if it is really a proof of P = NP.
Re: The 2-MAXSAT Problem Can Be Solved in Polynomial Time
#20Since the paper claims to give an algorithm for solving an NP-hard problem, e.g. it's a constructive proof, not just an existence proof, then presumably the author should be able to reduce some other problems to this one (2-Maxsat) and solve them as a demonstration.
Such a reduction is known to exist, but that doesn't mean it's necessarily easy to implement. It would suffice to find some large instances of 2-maxsat and solve those.