SoylentNews is people
SoylentNews
Researchers claim A Solution of the P versus NP Problem ( https://arxiv.org/abs/1708.03486) :
Berg and Ulfberg and Amano and Maruoka have used CNF-DNF-approximators to prove exponential lower bounds for the monotone network complexity of the clique function and of Andreev's function. We show that these approximators can be used to prove the same lower bound for their non-monotone network complexity. This implies P not equal NP.
The full journal article is available as a pdf on arXiv ( https://arxiv.org/pdf/1708.03486 ).
I recall studying computational complexity in college, so am attuned to the concepts of P versus NP being an outstanding issue, but cannot talk to what these researchers have found. I'm hoping a fellow Soylentil could shed some light on this finding and its implications. I notice the claim of "a" solution rather than "the" solution. I suspect this may be significant, but am unsure.
Here is some background information from Wikipedia's coverage of the P versus NP problem:
The P versus NP problem is a major unsolved problem in computer science. Informally speaking, it asks whether every problem whose solution can be quickly verified by a computer can also be quickly solved by a computer.
The underlying issues were first discussed in the 1950s, in letters from John Forbes Nash Jr. to the National Security Agency, and from Kurt Gödel to John von Neumann. The precise statement of the P versus NP problem was introduced in 1971 by Stephen Cook in his seminal paper "The complexity of theorem proving procedures"[2] and is considered by many to be the most important open problem in the field.[3] It is one of the seven Millennium Prize Problems selected by the Clay Mathematics Institute to carry a US$1,000,000 prize for the first correct solution.
The informal term quickly, used above, means the existence of an algorithm solving the task that runs in polynomial time, such that the time to complete the task varies as a polynomial function on the size of the input to the algorithm (as opposed to, say, exponential time). The general class of questions for which some algorithm can provide an answer in polynomial time is called "class P" or just "P". For some questions, there is no known way to find an answer quickly, but if one is provided with information showing what the answer is, it is possible to verify the answer quickly. The class of questions for which an answer can be verified in polynomial time is called NP, which stands for "nondeterministic polynomial time".[Note 1]
Consider the subset sum problem, an example of a problem that is easy to verify, but whose answer may be difficult to compute. Given a set of integers, does some nonempty subset of them sum to 0? For instance, does a subset of the set {−2, −3, 15, 14, 7, −10} add up to 0? The answer "yes, because the subset {−2, −3, −10, 15} adds up to zero" can be quickly verified with three additions. There is no known algorithm to find such a subset in polynomial time (there is one, however, in exponential time, which consists of 2n-n-1 tries), but such an algorithm exists if P = NP; hence this problem is in NP (quickly checkable) but not necessarily in P (quickly solvable).
An answer to the P = NP question would determine whether problems that can be verified in polynomial time, like the subset-sum problem, can also be solved in polynomial time. If it turned out that P ≠ NP, it would mean that there are problems in NP (such as NP-complete problems) that are harder to compute than to verify: they could not be solved in polynomial time, but the answer could be verified in polynomial time.
Aside from being an important problem in computational theory, a proof either way would have profound implications for mathematics, cryptography, algorithm research, artificial intelligence, game theory, multimedia processing, philosophy, economics and many other fields.
(Score: 5, Touché) by ledow on Tuesday August 15 2017, @09:05AM (2 children)
I'm a mathematics and computer science graduate, please don't lecture me on mathematical proofs.
It's like me turning up and saying "Hey, everyone, I solved world hunger!", after working in my shed for a day, and announcing it on Twitter. Yeah, mate. Course you did.
Progress in mathematics (and this is more maths than computer science) is made by proof.
That has a whole different meaning in mathematics, because any time you base your maths on things that aren't proven, they turn out to be bollocks that collapses quite quickly.
In this case, they're claiming P!=NP which impact upon MILLIONS of mathematical theories and basically "proves" maths (one way or another), cryptography, and a number of other areas. It's like someone claiming "Hey, guys, I just proved quantum loop gravity". The second all the physicists look at it, they will find a million holes and have it redacted for being nonsense, or not covering every angle.
You don't make progress in maths by making up nonsense, or by publishing one paper on arxiv (the mathematical equivalent of a tabloid paper). It has to be peer-reviewed by dozens of people, for years, and survive all such attacks. And then, in this case, it would quite literally change our understanding of mathematics. You don't just take it on trust that it's right.
That's not to say it's WRONG. It's just not PROVEN. Proof takes years. Because proof, quite literally, changes the fundamental base of EVERY other area of mathematics. If you get it wrong, you write a physics equation that blows up your spaceship, you hit a mathematical contradiction that means all your answers come out wrong, and you say something is impossible when actually it's trivial (e.g. in the field of cryptography, things like P!=NP are relevant to areas about whether elliptic curve cryptographs are "easy" to decrypt without the key - if this guy is RIGHT, he's proven that EC is secure. If he's wrong but we take his word, we could base an encryption scheme on something that - a few years from now - our enemies destroy because of a simple mathematical erroneous assumption).
P!=NP is literally the biggest thing in maths. We all SUSPECT it's true. We all HOPE it's true (or a lot of shit breaks). We all EXPECT it to be true. Proving it is quite literally saying "There will literally never be a way to do X, which has implications across every field of mathematics", which is a stupendous assertion for four random mathematicians on arxiv.
(Score: 0) by Anonymous Coward on Tuesday August 15 2017, @11:17AM (1 child)
(Score: 2) by Wootery on Tuesday August 15 2017, @01:46PM
You're very clearly completely outclassed. Go home, AC.