News for hackers. Stuff that matters.

A comment on The 2-Maxsat Problem Can Be Solved in Polynomial Time.

Re:The 2-Maxsat Problem Can Be Solved in Polynomial Time by jojohohanon on Thursday April 27, 2023 @11:39AM (#35729729)
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.

If you get a password in polynomial time you are golden.

[ Parent | on HN ]
Re:The 2-Maxsat Problem Can Be Solved in Polynomial Time by e79 on Thursday April 27, 2023 @11:56AM (#35729983)
The contest approach wouldn’t necessarily hold rigor, because it doesn’t formally prove that all 2-MAXSAT problems can be solved using this algorithm. Just that one or more cherry-picked problems can. I think the paper really just needs to present actual proofs for the propositions it makes (as others have pointed out).
[ Parent | on HN ]