> How could an attacker exploit this vulnerability?
> An unauthenticated attacker could exploit this vulnerability by sending a specially crafted packet to an affected service over the network. Successful exploitation could allow the attacker to execute code on the target system. No authentication or user interaction is required..
For example, the special theory of relativity doesn't work if space-time has any "lowest scale" (i.e. if the distance between any two events can be expressed as n * min_dist, where n is an integer and min_dist is a constant that has the same value for all observers), it you can't infinitely sub-divide it, since then lengths couldn't contract the way that the Lorrentz transforms predicts. Lots of math in QM and QFT also requires space and time to be continuous for other reasons as well.
Also, none of our current laws put any kind of limit on the life span of the Universe as a whole, so space-time is also infinitely increasing, even if heat death or big crunch models are correct.
Of course, none of this is provable per se - it is fundamentally impossible to run an experiment in finite time that proves whether something is finite or infinite. It could be that SR and QFT are wrong in their continuous space assumptions, but only in ways that are too subtle to measure. Still, as it stands, we don't have any theory of how the world works which allows for a discrete space-time, even as an approximation - we need space-time to be continuous for our current theories to work at all.
Well, our physics is famously incomplete and even if it weren't: math needing infinity is in no way shape or form proof of anything but the nature of math which itself could be nothing but a highly particular construct.
I always find it interesting nobody seriously questions why something so extraordinarily basic as geometry pervades "the universe". I'd say it's much more likely we are mathy creatures and cannot do anything but perceive logical building blocks somewhat reminding me of a guy using a flashlight proclaiming the universe comprises various configurations of spherical lights.
I can imagine infinity just fine and I'm sure many useful things can be inferred from it, but that doesn't mean it exists. Lots of math is possible but does not exist in reality and that's fine, I'm just being honest about the very real boundaries here. I get the feeling many people confuse the map for the territory.
This author seems to really mis-understand complexity theory and in what ways it matters. The choice of exponential = bad and polynomial = good may have been quasi-arbitrary initially, but it since found a much more solid footing.
Exponential complexity is what you automatically get when your algorithm is "generate a possible solution, verify if it's correct, repeat if it's not". Polynomial complexity is what you get when the problem itself has some kind of structure that you can exploit to either directly construct a solution, or to generate a very small set (relative to the problem size) of possible solutions that have to be checked by hand.
Now, it is true that for all practical problem-solving purposes, "P = NP but only with algorithms that require n^10^80 or more time (with this as a proven lower bound for even the typical case, no hope of improving)" would be exactly equivalent to "P != NP". However, it would still be a mathematically extremely interesting result, as it would tell you that any problem where it is easy to verify if a solution is correct carries some hidden structure that makes it "easy" to generate the solutions. And it could still open the door to finding new sub-classes of actually easy instances of these problems that are not known today, even if the worse case remains just as intractable.
Now, note the refutation of ETH with the new algorithm found by AI is not really that impressive, it doesn't seem to have that deep of an implication. Sub-exponential running times are not that fundamentally different from exponential ones - they basically just tell you that the problem has just enough structure to eliminate a certain class of possible solutions outright, instead of spending the time to actually verify them. If the algorithm found had been polynomial, even of a huge degree, this would have been a completely different discussion. As it is, we'll just replace the ETH with a "nearly-E"TH and nothing much changes.
Moreover, it was already known that some NP-complete problems admit sub-exponential algorithms. For example, planar graph 3-colorability can be solved in 2^O(sqrt(n)) time. This is not only sub-exponential, but vastly better than the running time of the new 3-SAT algorithm.
Still, the result is very interesting, since many problems can be solved asymptotically faster once subproblems that can be represented as 3-SAT can be solved faster. For example, we now have now have a deterministic interger factoring algorithm with run time N^o(1), where N is the integer being factored. Heuristic algorithms already achieved this bound, but the new claim is a deterministic worst-case guarantee. The result is a fairly straightforward application of the new 3-SAT solver.
> Moreover, it was already known that some NP-complete problems admit sub-exponential algorithms. For example, planar graph 3-colorability can be solved in 2^O(sqrt(n)) time. This is not only sub-exponential, but vastly better than the running time of the new 3-SAT algorithm.
I'm not real good at these sorts of details, but I'm struggling more than usual here. From what you say, and from things I think I know:
* Planar graph 3-colouring (P3COL) is NP-complete;
* Therefore 3-SAT can be reduced in polynomial time to P3COL;
* There is an algorithm for P3COL that runs in 2^O(sqrt(n)) time;
* Therefore there is an algorithm for 3-SAT that runs in 2^O(sqrt(n)).
> For example, we now have now have a deterministic interger factoring algorithm with run time N^o(1), where N is the integer being factored. Heuristic algorithms already achieved this bound, but the new claim is a deterministic worst-case guarantee. The result is a fairly straightforward application of the new 3-SAT solver.
This can't be true unless you're talking about unfathomably large integers, since the new 3SAT algorithm only improves on the 2^n bound for n > 10^100000000. That is, it's not in any way a practical algorithm that will ever be runnable on any possible computer.
> Exponential complexity is what you automatically get when your algorithm is "generate a possible solution, verify if it's correct, repeat if it's not".
I might be misunderstanding you, but this surely depends on the size of the candidate set in the problem. For a problem like "determine whether a given list of integers of length `n` contains a pair that sum to 100" the naive brute-force algorithm is polynomial. If you replace "pair" by "subset" then the naive brute-force algorithm becomes exponential.
Yes, I should have been more careful with the wording. Some problems have polynomial numbers of possible solutions, so for those there is no discussion of this kind. The more important point is that for some problems with a more-than-polynomial solution space (since even exponential is not precise enough, the solution space can be more than polynomial, such as n! for traveling salesman) we still have polynomial solutions, whereas for others we do not know of such algorithms.
The question can actually be generalized further - is it the case that for any solvable problem it's possible to find a solution without verifying every possible solution, and more specifically, only a tiny subset of the solution space? This would apply even beyond P vs NP, the same question would arise for EXP vs NEXP (that is, problems where we can find a solution vs just verify a given solution in exponential time), and same for factorial or Ackerman or any other complexity we want to imagine.
Looking at the problem in this way should also make it easier to construct a more strictly practical version of P vs NP, though it actually gets much harder to pin down details. That is, we can construct complexity classes that better match "what is plausibly solvable with a real computer" vs "what is plausibly verifiable with a real computer" and ask a similar question: given any problem of the second kind, can there be any generic algorithm of the first kind that would solve it?
Maybe I'm reading a bit too much into it but knowing it is NP (i.e. can be verified in polynomial time by a Turing machine) means it can be solved in polynomial time by a nondeterministic turing machine and there's at worst 2^N branches in it. Sort of. Giving a naive expectation of 2^N runtime times some polynomial. Which is exponential.
> However, it would still be a mathematically extremely interesting result, as it would tell you that any problem where it is easy to verify if a solution is correct carries some hidden structure that makes it "easy" to generate the solutions.
Your ""easy"" here means actually hard, not easy at all, so I don't think this is any evidence that it would be "extremely interesting".
And that's actually a point of the article: some problem being solvable by a polynomial algorithm was originally only interesting insofar it was a proxy for being easy. We were interested in easy solvability, not polinomiality itself. But now the proxy has mutated into an optimization target.
Even though we started with an intention of characterizing what is easy and what is not, we have come to understand that P = NP would actually be an extremely interesting result, mathematically even if not for practical engineering.
The point would be that it would prove that any problem can be solved without exploring all possible solutions, at least for problems whose solutions can be verified in polynomial time. Even more startlingly, since any problem in NP can be reduced to a problem in NP-complete (including all of the problems in NP-complete), it would mean that there exists a single algorithm that can solve any problem in NP without having to explore the entire solution space.
This would be an extremely startling discovery, even if the algorithm for doing so would turn out to have galactic complexity and thus no practical applicability. It would probably lead to a vastly different understanding about how problem solving works, and might turn out to have much more wide implications, such as in physics, perhaps even shedding some new light on whether quantum computing is really fundamentally more efficient than classical computing (which in turn is a question that has profound implications on the ties between classical and quantum mechanics, likely touching on the measurement problem).
Something is "carnivorous" if it directly consumes the flesh (or other parts) of an animal - usually a living one that it kills (as we have a different name for those that consume only already dead animals - necrophages).
Feeding on nutrients from an animal that died and was then broken down by other beings into base elements in the same area as your roots doesn't qualify these trees in any way as either "carnivorous" nor even "necrophage". Carnivorous plants are those that trap and kill animals that they then directly digest, such as a venus fly trap. Those don't just benefit from animals dying around them and being consumed by bacteria - they have mechanisms that cause the death of the animal and then secrete substances that directly convert the animal into plant nutrients.
Alt+F4 in Windows has always been "close window", not close app. It is even shown on the traditional "application icon" menu on each window, that many new apps are unfortunately doing away with.
> Alt+F4 in Windows has always been "close window", not close app.
Well, if we're talking about traditional Windows behavior, there's no such thing as an app in the first place.
Some programs allowed multiple windows to be open at the same time (e.g. Notepad), and some didn't (e.g. Paint), but for those that did, they spawned each window as its own process. Closing the window closed the process. That two processes shared the same executable had no deeper meaning until Windows XP added taskbar grouping.
Windows has had support for multiple windows in a single "app" (that is, a single C program that had one WinMain() function), from all points of view, since Windows 1.0. One sense is irrelevant here - all UI elements that we consider Controls today (such as a button) are "windows" in the standard Windows API. But even in what we normally call windows, these were present from the start of Windows 1.0: your application starts with one main window, and it can later create dialog windows, tiled windows, or popup windows - each of which can be closed without killing the main window.
Now, Alt+F4 didn't exist as a standard keyboard shortcut in Windows 1.0 - it was added later, but certainly by Windows 95 at the latest. And already in Windows 95, Alt+F4 was the "Close Active Window" shortcut, which would close the window or dialog that was currently active - not the entire application whose window this was. So pressing Alt+F4 on your keyboard while a "Save As" dialog was present in Word 95 would close that "Save As" dialog, it wouldn't close your Word document.
In Win16 all instances of executable shared memory (that's why there's hInstance in WinMain). But that should be transparent to user if implemented correctly.
Except Excel, which wants to act like single application with multiple windows.
Console applications, which do not have win32 windows with message pumps can be closed with alt-f4.
For GUI apps it sends a WM_CLOSE, because that's they way to "close" a GUI application.
For console applications it sends a message through the "Console control handler".
Which the console subsystem no longer lets the application properly handle and kills the process summarily anyway.
Note that I keep saying "application" because that has been the terminology in windows forever. "GUI apps" and "console apps" were a thing before mobile.
This is good detail, but I wasn't comparing to mobile, I was comparing to Macintosh. A native app on Windows has always been more of a loose collection of related files, whereas it is a single file on Macs and is presented as a cohesive unit throughout the operating system. Thus, Cmd+Q was more feasible than a similar shortcut could have been on Windows, and Alt+F4 really was its closest equivalent because Windows didn't organize things the way Mac did.
An "app" in Windows has always meant a process that starts with a WinMain() function. And as I said in other comments, a single app could always create multiple windows using the CreateWindow() function, that could each be independently closed (though not by Alt+F4). Nothing stops Windows in principle from having a way to close the entire application/process on pressing some keyboard shortcut regardless of which of its windows is currently in focus - they just didn't ever implement one. They could have defined a special message that the application's main message loop can handle to gracefully clean up everything, and then made a keyboard shortcut that would post this message, they just never did it.
No one is "responsible". If the paper is read, depends on the interest of the individual scientist. Many mathematicians interested in a theorem proven/disproven in a new AI paper will be curious, even if it is utterly cumbersome to extract the relevant line of thought. But don't you agree that the job can only be done by a mathematician anyway - be she/he paid by the company or by a university?!
What you are arguing for is somewhat like the "proprietary period" in astronomy (e.g. see https://www.scientificamerican.com/article/nasas-plan-to-mak... ). But there is no mathematician who asked for the run of AI, i.e. there is no mathematician, who can be regarded as the owner of the result, even if ownership was temporary. Complex proofs might take years to explain in detail (think of the ternary Goldbach problem, https://en.wikipedia.org/wiki/Goldbach%27s_weak_conjecture ). It's just unfair, if AI companies held back with their data until a proof has been put into a nicely readable article, and at the same time mathematicians elsewhere are spending all their time trying to solve it.
It's important to separate what can happen from what will happen.
The majority of people walking in the worse neighborhoods of LA or Chicago never have a single crime happen to them. But that doesn't mean that it's safe to go in a bad neighborhood - and it really doesn't mean it's safe to go there wearing designer clothing, gold watches, diamond rings and wearing your Apple VR device.
The same is true for travel. It's perfectly safe for the vast majority - but it's very important to be aware what may make you a target and what can happen to you if you are. Tens of millions of people visit the UK or China every year with no incident. But if you're a public active supporter of Palestine Action, or an active demonstrator against the CCCP respectively, be aware that you personally face a real risk from this travel, and your devices are actually very likely to be searched at those borders. Vice versa though (anti-CCCP activist traveling to UK, PA activist traveling to China) is perfectly safe, though.
Though I should note that this would be the "SSSR" since I was clearly using the latin alphabet, even if I had chosen to use the Russian name of the USSR.
That's completely different. Pleading the 5th and not testifying is completely different from giving false testimony - which is never protected. Even in a trial, if you are asked under oath if you handled the body, you are allowed to say that you invoke your 5th amendment rights not to respond; but you are not allowed to say "no, I didn't" if in fact you did (you can later be accused of perjury in addition to your conviction).
reply