Are you one of those people who equates any mention whatsoever of Trump as "being needlessly political"?
Not at all. But bringing him up in an unrelated post on a technical blog just screams "virtue signaling" to me.
I mean he also pokes fun at his children, himself, and posted a rap video about theoretical computer science on his blog. His blog is not exactly the Annals here... I think he is more than welcome to write about whatever he damn pleases and if you disagree you are more than welcome to argue in his comment sections (and more than likely lose)
> Nobody's really interested in a proof that P != NP. This is not the case. In my day job I need to worry about what happens if ECDSA is broken. One way that can happen is quantum computation -- but that has a relatively transparent development timeline we can plan for. The other way in which ECDSA could be broken is if P==NP and the discrete log problem can be transformed in polynomial time into another polynomial t…
Knowing P?NP does not imply much in practice unless the answer precisely bounds complexity. N^(N*1e-100) is exponential yet very practical while N^1e100 is polynomial yet is useless in this Universe.
This interpretation is wrong. The class P contains for example O(N^(10^100000!)), that are not "solvable" by any remotely reasonable meaning of the word.
This is true, but it's difficult to imagine what such a problem could look like. In reality, algorithms tend to come in discrete complexity "units" with very small terms. A linear algorithm isn't just fast -- it tells you something about how such an algorithm works and thus something important about the problem it solves. A quadratic algorithm can be interpreted as a "considers all pairs from the inputs" algorithm. A…
While not strictly in the same vein as O(n^10k), the constant factor in the proof that L=SL is 3^(2^65536) at the smallest. A lot of combinatorial problems can generate such algorithms, since they tend to rely on "we can solve this problem if this condition holds, we can make this condition hold for all inputs if we blow up our input with this large structure [which is technically constant time since the structure is fixed and not variant on size!]." Consider that this is the field of mathematics that produced a number that is "3 raised to itself so many times that I need to describe an algorithm just to write that number" that was used as the upper bound to a solution (the lower bound of which was 6).
I think it's even less useful, even if P = NP it is possible that no one finds an algorithm. Creating a (useful) algorithm is independent of proving the theorem. Also interesting is that someone could create an algorithm that solves NP complete in polynomial time without proving P=NP. They would be unable to prove the algorithm correct though.
This is correct. And, in fact, P=NP. However, while P=NP, the algorithm (oracle) resides on the other side of the event horizon. This is called the MAD paradox. https://nerdynotmad.com/p-equals-np/ The submitted proof will be found to be incorrect.
I haven't the foggiest idea what that "proof" is supposed to mean, I can't follow any step in it. What is MAD in this context?
> serious cahunas I think you mean "cojones" (which btw is a very rude word in Spanish). A kahuna is a kind of Hawai'ian shaman.
I stand corrected, thank you. I would normally have said "serious bollocks", but this forum is mostly left-ponders who would probably not have caught my drift.
North American here, we hear enough Brits speak to get the expression :)
I would normally sigh and move on seeing such a claim, but this guy is an established senior researcher at the University of Bonn. A career-ending disaster or instant and eternal fame, that's some serious cahunas.
There's a third possibility: there's a flaw in the proof, but one that is hard to find, and the discovery of the flaw actually advances the field in interesting ways. If I were a betting man that's actually where I'd put my money because the paper passes by bogometer test (but I am nowhere near qualified to assess whether it's actually correct).
I would normally sigh and move on seeing such a claim, but this guy is an established senior researcher at the University of Bonn. A career-ending disaster or instant and eternal fame, that's some serious cahunas.
There's a third possibility: there's a flaw in the proof, but one that is hard to find, and the discovery of the flaw actually advances the field in interesting ways. If I were a betting man that's actually where I'd put my money because the paper passes by bogometer test (but I am nowhere near qualified to assess whether it's actually correct).