The 2-MAXSAT Problem Can Be Solved in Polynomial Time
1–10 of 106 posts
Re: The 2-MAXSAT Problem Can Be Solved in Polynomial Time
#2P=NP alert
Re: The 2-MAXSAT Problem Can Be Solved in Polynomial Time
#3Also discussed a tiny bit yesterday https://news.ycombinator.com/item?id=35712326
Re: The 2-MAXSAT Problem Can Be Solved in Polynomial Time
#4Also discussed a tiny bit yesterday https://news.ycombinator.com/item?id=35712326
That's hardly a discussion.
The reality is yes it's an arxiv paper and I'm not a computational complexity expert so I cannot gauge it for myself.
Re: The 2-MAXSAT Problem Can Be Solved in Polynomial Time
#5P=NP alert
Which means something’s probably wrong with the proof, right?
Re: The 2-MAXSAT Problem Can Be Solved in Polynomial Time
#6Since 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.
Re: The 2-MAXSAT Problem Can Be Solved in Polynomial Time
#7P=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.
Re: The 2-MAXSAT Problem Can Be Solved in Polynomial Time
#8Usually 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.
Re: The 2-MAXSAT Problem Can Be Solved in Polynomial Time
#9Re: The 2-MAXSAT Problem Can Be Solved in Polynomial Time
#10Since 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.
If I read the paper correctly the 2-MAXSAT problem is usually referred to as MAX-2-SAT
https://en.wikipedia.org/wiki/2-satisfiability#Maximum-2-sat...