7 ms·
Poly-time algorithm for deciding Hilbert Nullstellensatz. A proof of P=NP
- xigoi 4y agoI'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.
- dls2016 4y ago"Ten Signs a Claimed Mathematical Breakthrough is Wrong" https://scottaaronson.blog/?p=304 https://scottaaronson.blog/?p=304 (I haven't looked at the paper linked in the title.)
- Tomte 4y ago8 applies, at least. It's like "you're interested in P = NP? I assume you've never heard of Turing machines, right?". And 7, of course.
- Jaxan 4y ago> it looks like it knows what it's talking about I’m not sure about that. I have never seen the notation Z_2 being used for the Gaussian integers, for example. Their notation is not quite standard and this is often a bad sign. Also the abstract on arxiv is full of latex commands…
- xigoi 4y ago> I have never seen the notation Z_2 being used for the Gaussian integers For some reason, my brain totally slipped over that when skimming the abstract. I was like “Gaussian integers are a real thing, ℤ₂ is a real thing, okay, cool”.
- pdpi 4y agoJust the citations alone (or rather the lack thereof) are enough to put this in the crank bucket.
- typest 4y agoGiven 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! Thus, I'm very skeptical of claims that P=NP.
- webkike 4y ago“Finding the proof is itself in NP” does not make sense as finding a singular proof is not something that depends on the size of its input, which is what the entire field of algorithmic complexity studies.
- bodhiandpysics1 4y agoIt actually does make sense, and is an important idea in complexity theory. In general, the problem of proving an arbitrary claim in ZFC isn't computable (this is just Godel's incompleteness theorem). if you confine your claims to smaller languages, you get smaller complexity classes. For instance, the problem of proving things in the propostional calculus is called BSAT, and is the quintessential NP complete problem. In general a nice way of thinking about what NP is are the set of formula that have polynomial time checkable proofs.
- bawolff 4y agoUmm. All proofs are in NP, not sure how that is relavent.
- bodhiandpysics1 4y agoNope... it depends on the language you use to write the proof. Agda proofs for instance are in R.
- bawolff 4y agoIs it really a proof (in the philosophical sense) if it cannot be verified in polynomial time?
- dontcontactme 4y agoIt's difficult to trust self-published, non-peer reviewed papers on arxiv. You can just as easily find papers claiming P=/=NP https://arxiv.org/abs/2108.09269 https://arxiv.org/abs/2108.09269
- bilsbie 4y agoWouldn’t this be easy to test though?
- bawolff 4y agoNot just that, but this paticulary problem is also famous for crazy people claiming they have a proof. Until some mathmatician agrees with the proof (or even just indicates it is interesting), this is a non story.
- jsmith45 4y agoYeah. The "proof" of theorem 2 being just a handwavy do the first proof again, but use Q_2 and normalize the result after each step to a simple fraction, which will only increase c_1. That really sounds suspicious to me. Why not just solve this version directly with these changes. That should have been a more straightforward proof.
- WoahNoun 4y agoThis paper is bad. 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.)
- heinrichhartman 4y agoCan you pin-point the first error?
- WoahNoun 4y agoThat's not a valid argument against a paper being bad.
- heinrichhartman 4y agoThat was an honest question. I agree the paper is bad, but I struggle to find the first mistake.
- WoahNoun 4y agoI'm gonna guess it's the assumption that the intermediate steps of the algo can determine that a solution doesn't exist. >As usual, if the solution does not exist, the process is terminated with a message "No solution at Level 2, Identity 2"
- xigoi 4y agoNot everyone has the necessary background to see what's wrong with it.
- WoahNoun 4y agoBut anyone who has read enough math and cs papers can see that this paper is clearly badly structured, written, and organized. It is a bad paper regardless of the correctness of the argument.
- 4y ago
- bawolff 4y agoSo just from the headline, "unknown person solves p=np" there is a 99.9999% chance this is wrong. 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?
- paulpauper 4y agono. they may still be impractically unsolvable
- Reventlov 4y agoYeah, P=NP says nothing about the possibly enormous constant factor in front of your poly-time algorithm.
- bodhiandpysics1 4y agoNp hard problems aren't that hard to solve. I'm solving one right now actually for work (graph bi-partition using simulated annealing), and it doesn't even take that long. Of course my algorithm isn't actually correct! Or if I had a correct algorithm it might be really fast but still not have polynomial growth. You need a proof.
- bawolff 4y agoYou need the proof to show it really works in all cases. However if the goal is some quick (non-exhaustive) verification, then why can't you just use the algorithm? (Ignoring the big constants, high degree polynomial issue siblings mention). Either A, it doesn't work, showing the paper is incorrect. Or B it works, showing that even if it doesn't prove the paper fully correct, it shows that at least something interesting is going on.
- kraghen 4y agoThe 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.
- ogogmad 4y agoThis might be it. Good catch. A machine that can perform all integer arithmetic operations (+, -, *) in constant time can solve all problems in PSPACE in polynomial time.
- silasdavis 4y agoYes I think this is where NP is hiding.
- bodhiandphysics 4y agoWe’re lucky he didn’t claim p=PSPACE!
- teraflop 4y agoYup. Just at a glance, I don't see even a cursory attempt to prove that the upper bound on the proposed algorithm's time complexity is actually a polynomial. It depends on the "serial numbers of [...] monomials, in the natural order of monomials". But the number of different possible monomials in a polynomial with bounded length is obviously exponential. The closest the paper gets to actually talking about time complexity is: > As it is mentioned in [3], there is no sense to make use of the formal definition of Turing machine for this problem. From practical point of view, it is much more useful to show existence of a polynomial-time constructive algorithm for solving it ([2]). Therefore, in the next section we will introduce our own definitions and notations, describing a kind of a formal computer, more practically oriented, but resembling that of a Turing machine. But the so-called "formal computer" is only described in extremely hand-wavy and informal terms, and no attempt is made to relate the number of "steps" it would perform to the running time of a corresponding Turing machine.
- abeppu 4y agoSo 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. 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. _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?
- paulpauper 4y agoThis 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.
- blt 4y agoIt'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?
- nix0n 4y agoThe line about "the process terminates with a message", suggests to me that source code for this algorithm does exist. I think the algorithm is probably NP but it still could be useful for solving NP-hard problems.
- throwaway81523 4y agoMy 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. 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. 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. See also: https://en.wikipedia.org/wiki/Blum%E2%80%93Shub%E2%80%93Smale_machine https://en.wikipedia.org/wiki/Blum%E2%80%93Shub%E2%80%93Smal...
- slaymaker1907 4y agoThe 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).