1. 5

  2. 5

    I’ll get excited about it when I see someone a lot more knowledgeable in this space gets excited.

    1. 5

      Another paper to add to the list of claimed proofs of the N vs. NP problem:


      1. 2

        … What? SAT is already NP-complete. This paper talks about constructing a problem related to SAT and proving that that problem is also NP-hard. As far as I was able to digest from my quick read, it does nothing to establish the relationship of the new problem to SAT in terms of complexity, and it’s hard to see how that approach could prove anything about P even if it did.

        The writing is also kind of unclear, but I’m hesitant to ding a preprint just for that because it’s possible that English is not the first language of its author. But of course for a paper on a topic this important to be taken seriously, it would almost have to have perfect writing and come from a well-known name in the field.

        1. 5

          The paper is better than that, but there is still probably a mistake. I mean, a serious one, because I have already found a fixable one.

          1. The author defines yet another NP-Complete function. I think it is even claimed to be previously known.

          2. The author says that the new literal-compatibility-satisfiability is «isotonic» — nondecreasing in every variable.

          3. The author remarks that polynomial-time algorithm implies a polynomial-size boolean circuit.

          4. The author claims that a boolean circuit for a non-decreasing function can be built out of AND and OR with a constant overhead compared to the optimal circuit. The proof ends up listing some NOT operations in the final count… I will not be surprised if this is fixable, but that is a warning sign that not all the details are fully polished yet.

          5. The author presents a way to assign weights to all the elements of an AND-OR circuit for the NP-Complete function in question; the claim is that every element has a polynomial weight but the total weight is exponential. There is nothing apriori wrong with such an approach.

          (4) has a typo-level mistake and (5) could easily hide a few mistakes. I am not currently in the mood to check, and statistically it is likely that there are mistakes and someone will post a detailed explanation next week. Or maybe (4) is actually substantially wrong.

          1. 1

            Interesting. I appreciate your explanation, I wasn’t able to focus on it enough to understand that.