Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[Arx]

Possible proof that P =/= NP.

Which is being treated with cautious optimism at the moment, as far as I know.

[MetalSlimeHunt]

I spent a few minutes trying to decrypt that paper description and only gave myself a nosebleed. Though I'm not entirely sure P != NP is a good thing, if the case I'd start considering it the number one most likely answer to the Fermi Paradox.

[Arx]

It's kind of a neutral thing. Currently it's mostly academic, I think - whether P=NP or not doesn't matter if we can't find the P variants anyway.

And don't feel bad about not following. My sister spent about an hour working on the paper and made it seven pages in, as someone who's studied this kind of thing before.

[Max™]

I think they're using a way to prove that they can show a lower bound on one of the two members of NP they discussed, and show how converting one of them to P gives the inequality, but I haven't been awake long enough to be sure I was parsing remotely to correctly and it's been years since I crunched on a paper as dense as that one (x-rays of the riemannian zeta function incidentally, fascinating stuff) but if it's true then it's something of a relief. P=NP is kinda scary if you like encryption and such.

[Arx]

In principle, the proof is really simple: they assert that the problem is NP-complete, and that they have proved that the lower bound is NP. Thus P =/= NP.

The reason the computing world is not collectively flipping all the way out (although this is causing a bit of a stir) is that it's possible that a) the problem is not, in fact, NP-complete and/or b) the assumptions used to prove the lower bound are flawed and thus there may be still be a polynomial lower bound.

[Telgin]

This is an exciting development if the paper isn't flawed, but there very likely is an error in it somewhere just going off of history.  It's not an exciting result since almost everyone expected that P != NP, but it's still exciting if someone can prove it.

I wish I'd studied this material more in grad school, but my focus was on HPC instead so I probably couldn't parse the paper fully if I even had the academic energy left in me to read all 38 pages of it.

[smjjames]

Dutch Scientists from the Eindhoven institute for fundamental energy research, 'Differ', might have found the solution to one of the big problems with fusion energy reactors: keeping the reactor walls cool, or in other words, finding a material that can withstand being exposed to temperatures comparable to the surface of the sun for long periods of time.

They discovered that by adding liquid tin to a spongelike structure made of wolfram, not only did the divertor (basically, a fusion reactor's exhaust) stay cooler, it also gained the ability to self-repair.

The liquid tin furthermore forms a cloud of tin gas, acting as a shield barrier, catching the high energy outburst from the reactor before they can hit the actuall wall, and dispersing the incoming energy evenly.

Sadly the breakthrough comes too late to be incorporated in the Iter test reactor, scheduled (after many delays and setbacks) to first start testing in 2025. If further testing proves viable, it might very well be used in the Demo test reactor planned for 2050.

I don't suppose they could share that knowledge so that others who can apply it to their reactors can do so? And yeah, I know everybody is in a race (insofar as the whole thing can be called a race) to build a functioning reactor with power output and don't really want to share their stuff.

[Eric Blank]

I'm not asking if you'd cook, I'm asking if it would feel pleasant to sleep on the ground on a cool summer night. For reasons.

No, because basalt gravel is uncomfortable as fuck.

[martinuzz]

Dutch Scientists from the Eindhoven institute for fundamental energy research, 'Differ', might have found the solution to one of the big problems with fusion energy reactors: keeping the reactor walls cool, or in other words, finding a material that can withstand being exposed to temperatures comparable to the surface of the sun for long periods of time.

They discovered that by adding liquid tin to a spongelike structure made of wolfram, not only did the divertor (basically, a fusion reactor's exhaust) stay cooler, it also gained the ability to self-repair.

The liquid tin furthermore forms a cloud of tin gas, acting as a shield barrier, catching the high energy outburst from the reactor before they can hit the actuall wall, and dispersing the incoming energy evenly.

Sadly the breakthrough comes too late to be incorporated in the Iter test reactor, scheduled (after many delays and setbacks) to first start testing in 2025. If further testing proves viable, it might very well be used in the Demo test reactor planned for 2050.

I don't suppose they could share that knowledge so that others who can apply it to their reactors can do so? And yeah, I know everybody is in a race (insofar as the whole thing can be called a race) to build a functioning reactor with power output and don't really want to share their stuff.

I'm quite sure they will share it. Government is pushing hard over the past few years even to make Dutch scientists publish their research in open access media.
Don't know what makes you think they wouldn't share it. The Netherlands isn't China.

[sluissa]

Can someone explain the P=/=NP thingymajig?

I have no fucking clue what it's on about, and the paper summary didn't help.

No expert myself, but based on what I understand you basically have two things they're trying to prove are or are not equal.

You have problems that can be solved by a computer. And you have problems that if a computer is given the answer to a question, the computer can verify that answer.

The challenge was to prove definitively whether those two sets of problems overlap completely (P = NP) or do not overlap completely P != NP.

As to the use or importance of this proof. I can't say. But from what I understand it's more of a academic thing than anything else. There was also a $1,000,000 prize attached to solving it, which gave it a bit of a higher profile than most of these sorts of problems.

Please though, someone explain it better than I because I feel like I'm only partially grasping it.

[Draignean]

Well, something to keep in mind. There are 116 proofs of either P=NP or P≠NP as of September 2016.

Although we can be reasonably certain that the ones of  P=NP are bunk since the writers do not (as yet) rule the cybersecurity world.

[Trekkin]

Here's my best attempt to put it into layman's terms:

We're looking at two sets of problems here, categorized by computational complexity; i.e. how much longer it takes to solve a particular kind of problem as you make the input set bigger. This is related to the idea of big-O notation; for a toy example, if I am looking for the biggest number in an unsorted array, I need to check every number, so it's O(n); it takes twice as long for an array twice as big. If it's sorted, though, it's O(1); no matter how big the array is (and ignoring the speed at which it can be accessed), it's going to take the same amount of time to pull up the first (or last) element.

P refers to the set of problems for which the big-O notation is O(n^k) for some constant k; in other words, they are solvable in polynomial time for a deterministic computer. These problems, among which number selection sort and maximum matching, are (loosely speaking) efficiently solvable, or at least solvable with predictable efficiency, by computers we can actually build.

NP is P but for a computer that isn't deterministic; that is to say, for a computer that can choose to do two different things based on the same input -- and magically choose the more useful one. Naturally, we do not have these computers -- and before anyone brings it up, no, quantum computers are not the same thing as nondeterministic computers. If we did, though, have computers that could intelligently choose to do different things with the same input and always pick the right thing, we could solve what are called NP-hard problems in predictable time. Instead, NP-hard problems can be solved by generating random solutions, the verification of which is not itself NP -- but nobody knows how long that's going to take. NP-hard problems are interconvertible, too, so a polynomial solution to one of them could solve all of them.

P=NP, it would utterly break most of the cryptography people use day to day (although not all of the cryptography we could use); primality testing is P but factoring is NP, so if P=NP we can determine everybody's private keys and read encrypted messages and destroy our current ability to securely send and receive information. One-way functions also depend on P != NP, so all our password hash functions would be useless too. It would allow for efficient solutions of traveling salesman, though, and some folding problems, so that would be nice. There are other implications but they're mostly too arcane to explain here.

On the other hand, if P != NP (as is increasingly likely)...not much changes, except that we don't need to worry about if P=NP. We may not need to worry about it anyway; just because a problem is polynomial does not mean it is easily solved with computers we actually have.

In the most banal of "practical terms", it won't matter to people outside of STEM either way; the kinds of problems a constructive proof of P=NP would make it more efficient to solve aren't the sorts of things most people solve, and we have stochastic ways of solving specific cases of NP-hard problems now, much as we do for problems in P where k is too large to bother solving optimally.

[Trekkin]

I think the matter wasn't one of trying to put an explanation of P versus NP into layman's terms, but that earlier paper.

Ah. I assumed that by

Can someone explain the P=/=NP thingymajig?

greatorder meant "the unsolved problem of P ?= NP", not that particular paper.

[Starver]

So long as N≠1 and P≠0, P≠NP.

S'obvious!

(jk)

[Egan_BW]

I appreciated that explanation of P=NP! I never understood what it means before, but I didn't know where to look for an explanation I would understand.