TE
TechEcho
Home24h TopNewestBestAskShowJobs
GitHubTwitter
Home

TechEcho

A tech news platform built with Next.js, providing global tech news and discussions.

GitHubTwitter

Home

HomeNewestBestAskShowJobs

Resources

HackerNews APIOriginal HackerNewsNext.js

© 2025 TechEcho. All rights reserved.

The 2-MAXSAT Problem Can Be Solved in Polynomial Time

61 pointsby 9NRtKyP4about 2 years ago

16 comments

tgflynnabout 2 years ago
I&#x27;ve spent a great deal of time over the last decade+ trying to find an efficient algorithm for NP hard problems and one thing I&#x27;ve learned is that this field is a graveyard for seemingly good ideas. Therefore I tend to be very skeptical of any paper that claims to solve such a problem but doesn&#x27;t provide any empirical evidence that their solution works. I mean I&#x27;ve had hundreds of ideas and very few of them have survived without counterexamples appearing even for very small instance sizes.<p>I first saw this paper yesterday when it was posted on HN but didn&#x27;t make it to the front page and I&#x27;m uncertain about how much energy to put into it (unfortunately my health gives me very little to spare). So far I&#x27;ve only read the introduction and it doesn&#x27;t obviously involve any advanced mathematics that I&#x27;m unfamiliar with so I could perhaps attempt an implementation.<p>In addition to what I said above another factor arguing against investing much time in this is the fact that this was first published last year and nothing seems to have come of it in that time. Moreover it appears that the current paper is a revision from the one that was published last year. Does anyone know what the history of this was ? Were bugs found in the first version ?
评论 #35730178 未加载
pfedakabout 2 years ago
Unsurprisingly, there&#x27;s nothing here. Most of the paper describes a brute force search across all possible variable assignments in the form of a graph (with some pointless polynomial improvements like making it a trie), where you build a path of vertices representing each set of truth values that satisfies a given expression. This clearly has exponential size, which the author alludes to in the &quot;improvements&quot; section by noting it does &quot;redundant work&quot;. This is addressed by collapsing the exponential graph down to have only one vertex for each variable*expression pair (if you ignore the trie) and adding exponentially many labels for the different paths to reach a given vertex. (incidentally, to the extent that it&#x27;s described clearly, it seems like the improved layered graph would basically be the same as the original non-layered graph)<p>The final complexity discussion uses the graph size constraint gained by the &quot;improvement&quot; but doesn&#x27;t consider how to handle the extra labeling meaningfully. Basically, the pre- and post-improvement algorithms put the exponential work in different spots, and the sloppiness of the algorithm description (I mean, really, why tell us you&#x27;re using a stack for BFS and then have &quot;determine the subset of satisfied constraints&quot; as a step) makes it easy to ignore.<p>I&#x27;m also being a little generous with the algorithm itself. As described, some of the trie optimizations seem to make certain combinations of satisfied expressions impossible to notice, but I think it&#x27;s not a big deal to make this part work. The properties of the trie structure (and of sorting the variables by occurrence, for that matter) don&#x27;t seem to be used.
评论 #35752579 未加载
评论 #35735854 未加载
mabboabout 2 years ago
I have a hard time taking seriously anyone who publishes a paper like this truly believing they&#x27;ve solved P=NP.<p>Remember the &quot;faster than light neutrinos&quot; thing? They published their stuff basically saying &quot;Okay, we&#x27;re really uncomfortable with this result so can someone explain what we&#x27;ve missed here?&quot;.<p>Papers like this always feel like the author is surprised anyone is even doubting them. &quot;What, it&#x27;s just the hardest problem in your field, worthy of a Millennium prize, and I&#x27;m publishing it in some lesser-known journals with little peer review. What of it?&quot;<p>Come on. Have some modesty. Have some self-doubt! Reach out to Terry Tao and you know he&#x27;ll happily explain your mistake and then help you write a better paper.
评论 #35729863 未加载
rliliabout 2 years ago
For me, the following is a bit that seems particularly prone to be invalidated, even more so considering that the author doesn&#x27;t present any proof of it:<p>&gt; Here, we notice that if we had one more span, &lt;v3 , v4 , v5 &gt;, for example, it would be connected to &lt;v1 , v2 , v3 &gt;, but not overlapped with &lt;v1 , v2 , v3 &gt;. Being aware of this difference is important since the overlapped spans imply the consecutive ‘<i>’s, just like &lt;v1, v1, v2&gt; and &lt;v1, v2, v3&gt;, which correspond to two consecutive ‘</i>’s: (c2 , <i>) and (c3 , </i>). 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.
评论 #35729406 未加载
评论 #35728655 未加载
Ono-Sendaiabout 2 years ago
Since the paper claims to give an algorithm for solving an NP-hard problem, e.g. it&#x27;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.
评论 #35728611 未加载
评论 #35728290 未加载
评论 #35728783 未加载
chriskananabout 2 years ago
Usually 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&#x27;t seem to work in computer science theory.<p>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.
评论 #35728354 未加载
评论 #35730146 未加载
karmakurtisaaniabout 2 years ago
Ah, but the question of P=NP has been already settled several times even, and as P!=NP too, see <a href="https:&#x2F;&#x2F;www.win.tue.nl&#x2F;~wscor&#x2F;woeginger&#x2F;P-versus-NP.htm" rel="nofollow">https:&#x2F;&#x2F;www.win.tue.nl&#x2F;~wscor&#x2F;woeginger&#x2F;P-versus-NP.htm</a><p>(To the ones who did not waste their best years doing theoretical computer science, this was in jest - the paper most definitely contains mistakes)
js8about 2 years ago
Well, this is somewhat heartbreaking for me. I haven&#x27;t read the paper, but the result sounds very plausible to me.<p>I am also an amateur working on P=NP. Last week, I think I also proved that P=NP, but with a different method, and was about to seek publication.<p>My result seems very similar to his, yet very different. I can prove that class of SAT which is intersection of 2SAT and XORSAT is NP-complete by reduction to 3-SAT. Then I follow the approach in Melville&#x27;s Krom 1967 paper on 2-SAT, and prove that certain polynomial-sized logic (that corresponds to the intersection) is refutable complete. So you can essentially generate all formulas in that logic and if you don&#x27;t find contradiction, the instance is satisfiable.<p>I have also did some preliminary testing of my method, and was able to factor small integers with it. However, there was a bug.<p>So, to sum up, I am not surprised that P=NP with a constructive and efficient algorithm. Take it for what you want. The future is gonna be interesting (crypto DOOMSDAY).
评论 #35729912 未加载
评论 #35730280 未加载
评论 #35732868 未加载
erk__about 2 years ago
Also discussed a tiny bit yesterday <a href="https:&#x2F;&#x2F;news.ycombinator.com&#x2F;item?id=35712326" rel="nofollow">https:&#x2F;&#x2F;news.ycombinator.com&#x2F;item?id=35712326</a>
评论 #35728028 未加载
MPSimmonsabout 2 years ago
&gt;By the MAXSAT problem, we are given a set V of m variables and a collection C of n clauses over V. We will seek a truth assignment to maximize the number of satisfied clauses. This problem is NP-hard even for its restricted version, the 2-MAXSAT problem by which every clause contains at most 2 literals. In this paper, we discuss a polynomial time algorithm to solve this problem. Its time complexity is bounded by O(n2m3). Hence, we provide a proof of P = NP.<p>Talk about burying the lede.
jojohohanonabout 2 years ago
The first step is to encode some decent password cracking challenge into an NP complete problem - choose 3 SAT or something similarly well understood. Then encode that 3sat problem into the paper’s solution domain.<p>If you get a password in polynomial time you are golden.
评论 #35729983 未加载
haliskerbasabout 2 years ago
One of you is going to turn this into a puzzle and ask me in my next interview. I won&#x27;t know the answer, but please don&#x27;t laugh at me when you realize!
geophileabout 2 years ago
P=NP alert
评论 #35729081 未加载
评论 #35728161 未加载
评论 #35728113 未加载
marcodiegoabout 2 years ago
&quot;Hence, we provide a proof of P = NP.&quot;<p>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.
评论 #35729161 未加载
hota_maziabout 2 years ago
&gt; Hence, we provide a proof of P = NP.<p>Is this serious?
rsrsrs86about 2 years ago
No proof inside?