So just from the headline, "unknown person solves p=np" there is a 99.9999% chance this is wrong.<p>However if i read the first sentence of the abstract correctly, they are claiming to have a constructive proof (i.e. they found an algorith). So can't we just check the proof by using their alleged algorithm on some np-hard problems?
The definition of "basic step", which includes arithmetic on unbounded integers, is suspicious. And I don't see any attempt at establishing an upper bound on the size of coefficients. I wouldn't be surprised if they grow exponentially.
It's difficult to trust self-published, non-peer reviewed papers on arxiv. You can just as easily find papers claiming P=/=NP<p><a href="https://arxiv.org/abs/2108.09269" rel="nofollow">https://arxiv.org/abs/2108.09269</a>
I've learned to be cautious about supposed proofs of famous conjectures, especially if they're published by one person who is not a well-known mathematician, but I don't know nearly enough about this topic to judge this one and it looks like it knows what it's talking about. I'm curious how it turns out.
My first thought from the title was that this result is in the Blum-Shub-Smale computational model rather than the traditional Turing machine model. In the BSS model, arithmetic operations on exact real numbers are done in constant time. That is useful for analyzing numerical algorithms where you are more interested in e.g. convergence speed than things like roundoff errors. But the exact real arithmetic in constant time is equivalent to doing infinite-precision integer arithmetic in constant time. A couple of people already have mentioned the latter as an assumption of the paper as if that were a big error, but in the BSS model it is part of the deal. Thus the BSS model gives speedups for some problem classes and it's not a big surprise that P=NP there.<p>I didn't realize P vs NP was supposed to be an open problem in the BSS model. I thught that this solution was an early result. The catch is simply that it doesn't apply to the Turing machine model which is what most people think of when they hear of P vs NP.<p>There is a wonderful and mathematically accessible book from the 1990s about the BSS model: Complexity and Real Computation, by Lenore Blum, Felipe Cucker, Michael Shub, and Steve Smale. I thought it was going to open up into a big field, but I don't know if much happened with it.<p>See also: <a href="https://en.wikipedia.org/wiki/Blum%E2%80%93Shub%E2%80%93Smale_machine" rel="nofollow">https://en.wikipedia.org/wiki/Blum%E2%80%93Shub%E2%80%93Smal...</a>
Given how many people have failed to prove P=NP, and how strange the world would look if P did equal NP, it seems very likely that P!=NP. This would also help explain why it's so hard to prove P!=NP -- finding the proof is itself in NP!<p>Thus, I'm very skeptical of claims that P=NP.
This is wrong. For a proof of polynomial time requires steps to construct the actual computable function. This paper does not do that. It simply shows that it's possible to solve a system of equation in some finite number of steps, but this tells you nothing about construction of the finite polynomial algorithm. All this proves is Gaussian elimination is o(N^3) which is well -established.
So a meta question is ... recently there was a bit of a hubbub about arxiv not posting preprints from academics with findings critical of the big bang. The claim was basically that arxiv isn't supposed to be refereed or edited that way, and that discussions that are at odds with established mainstream views should still be accepted.<p>At the other end of the spectrum, the USPTO won't look into anyone's claim to have invented a perpetual motion device. And the social networks will flag me if I claim that my one cool trick will stop covid transmission. Sometimes you don't have to look closely into a claim to be pretty sure it's false, and possibly harmful in some way.<p>_Should_ there be any upstream filtering on arxiv posting when an unknown person claims to have an extremely surprising result, and their reference list suggests that they may be disconnected from the literature in the relevant field? Is there any kind of claim that _should_ be proactively rejected?
It's already suspicious that the author left a bunch of non-math LaTeX commands in the abstract on arXiv. You proved one of the most important open questions in the history of humanity, but couldn't be bothered to make sure the abstract looks presentable?
The line about "the process terminates with a message", suggests to me that source code for this algorithm does exist.<p>I think the algorithm is probably NP but it still could be useful for solving NP-hard problems.
The author also published a paper last year claiming to prove Sendov's Conjecture that has not been published in an actual journal (as far as I can tell anyway).
This paper is bad.<p>Edit: For a math paper, this paper is badly written, structured, and organized even if the argument turns out to be correct. (Which is ~0% chance.)