Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Machine learning leads mathematicians to unsolvable problem

nature.com

Post reply on HN
Print view View original

51–60 of 98 posts

Re: Machine learning leads mathematicians to unsolvable problem

#51

Post by [deleted] »

eanzenberg wrote: post #38
CuriousCosmic wrote: post #31

Earlier quoted context omitted.

and fees for publishing. i.e. Why should people have to pay to view the results of what is often publicly funded research? Even more so why should researchers have to pay to publish work that the publishers profit off of but the researchers don't.

Because being a peer reviewer shouldn’t be done for free? Do you like being paid to work? Because Nature has established themselves as a premier journal over the the past 150 years and are known for their quality? Or maybe I’m just taking crazy pills..

[deleted]

Re: Machine learning leads mathematicians to unsolvable problem

#52

Post by curiousStarDust »

elliotec wrote: post #48
curiousStarDust wrote: post #46

Not completely on the subject, but I had to read the first sentence 5 times, before I was able to understand its meaning. Then I realized it was too long, so modified it to following version. Is it better or worse? "A team of researchers has stumbled on a question that is mathematically unanswerable. It is linked to logical paradoxes, that were discovered by Austrian mathematician Kurt Gödel in the 1930s and it can’t…

Yeah, it’s a bit better. Not sure how much, maybe more for non native speakers?

Thanks! English is my 3rd language, so I do struggle with reading sometimes.

Re: Machine learning leads mathematicians to unsolvable problem

#53

Post by kortilla »

eanzenberg wrote: post #38
CuriousCosmic wrote: post #31

Earlier quoted context omitted.

and fees for publishing. i.e. Why should people have to pay to view the results of what is often publicly funded research? Even more so why should researchers have to pay to publish work that the publishers profit off of but the researchers don't.

Because being a peer reviewer shouldn’t be done for free? Do you like being paid to work? Because Nature has established themselves as a premier journal over the the past 150 years and are known for their quality? Or maybe I’m just taking crazy pills..

>Or maybe I’m just taking crazy pills..

You are. Where did you ever get the idea that nature pays for reviews?

Re: Machine learning leads mathematicians to unsolvable problem

#54

Post by fspeech »

diegoperini wrote: post #50
foxrob92 wrote: post #40

Earlier quoted context omitted.

I mean, haven't the authors shown that the problem is "worse" than NP-hard? They have shown it to be undecidable?

How is worse than NP-hard named in the field? NP-impossible? Disclaimer: I'm really noob, not asking it sarcastically.

Undecidable means there is no logical way to have an answer. Turing’s halting problem is one such.

Re: Machine learning leads mathematicians to unsolvable problem

#55

Post by raverbashing »

chaboud wrote: post #39

One doesn't need to go back to Gödel for this to make it a "huh" moment. Instead, go back to 2006 to make it a "duh" moment. Aggregability is NP-Hard: https://www.google.com/url?sa=t&source=web&rct=j&url=http://... That is, even for linear systems, determining whether or not macrovariables (e.g. complete eigenvector sets, complete embeddings) exist for a given space is an NP-Hard problem. With linear systems serving…

An NP-hard problem is still possible to be solved. Impractical but possible.

An undecideable solution cannot be proven true.

Re: Machine learning leads mathematicians to unsolvable problem

#56

Post by miclill »

Cacti wrote: post #47
chaboud wrote: post #39

One doesn't need to go back to Gödel for this to make it a "huh" moment. Instead, go back to 2006 to make it a "duh" moment. Aggregability is NP-Hard: https://www.google.com/url?sa=t&source=web&rct=j&url=http://... That is, even for linear systems, determining whether or not macrovariables (e.g. complete eigenvector sets, complete embeddings) exist for a given space is an NP-Hard problem. With linear systems serving…

NP-hard and undecidability are completely different things. They’re barely on the same planet.

I would argue that for practitioners it is the same planet. But I agree that they are not the same thing.

Re: Machine learning leads mathematicians to unsolvable problem

#57

Post by shoo »

miclill wrote: post #56
Cacti wrote: post #47

Earlier quoted context omitted.

NP-hard and undecidability are completely different things. They’re barely on the same planet.

I would argue that for practitioners it is the same planet. But I agree that they are not the same thing.

disagree, some small size NP-hard problems can be solved in practise.

or, given enough effort / luck / redefining the problem, sometimes extra structure can be found for the particular problem instances that you want to solve, meaning that they actually belong to an easier problem class that can be solved in practise -- e.g. you've got extra information or constraints that you're not actually using, so you don't need to solve the NP-hard problem in general, just solve the specific problem you've got.

i'll willing to change my position if someone can argue it is similar for undecidable problems.

Re: Machine learning leads mathematicians to unsolvable problem

#58

Post by vinceguidry »

fspeech wrote: post #54
diegoperini wrote: post #50

Earlier quoted context omitted.

How is worse than NP-hard named in the field? NP-impossible? Disclaimer: I'm really noob, not asking it sarcastically.

Undecidable means there is no logical way to have an answer. Turing’s halting problem is one such.

There's got to be more to it than that. The halting problem itself isn't some on-off switch, it can be studied and broken down into different problem classes, some of which are indeed decidable.

It's just impossible to write a general-purpose algorithm to solve it in all cases.

Re: Machine learning leads mathematicians to unsolvable problem

#59

Post by pfortuny »

shoo wrote: post #57
miclill wrote: post #56

Earlier quoted context omitted.

I would argue that for practitioners it is the same planet. But I agree that they are not the same thing.

disagree, some small size NP-hard problems can be solved in practise. or, given enough effort / luck / redefining the problem, sometimes extra structure can be found for the particular problem instances that you want to solve, meaning that they actually belong to an easier problem class that can be solved in practise -- e.g. you've got extra information or constraints that you're not actually using, so you don't need…

Well: the halting problem is undecidable. That does not prevent us to try and prove (many many times) that an algorithm does or does not stop.

I guess the parent meant something like this.

Of course the concepts are totally dissimilar but the practical consequences are less apart.

Re: Machine learning leads mathematicians to unsolvable problem

#60

Post by pfortuny »

raverbashing wrote: post #55
chaboud wrote: post #39

One doesn't need to go back to Gödel for this to make it a "huh" moment. Instead, go back to 2006 to make it a "duh" moment. Aggregability is NP-Hard: https://www.google.com/url?sa=t&source=web&rct=j&url=http://... That is, even for linear systems, determining whether or not macrovariables (e.g. complete eigenvector sets, complete embeddings) exist for a given space is an NP-Hard problem. With linear systems serving…

An NP-hard problem is still possible to be solved. Impractical but possible. An undecideable solution cannot be proven true.

Yes but there are very fee practical instances of undecidable problems (by instance I mean a specific concrete here-are-the-numbers problem, not a general statement about “equations”).
Post reply on HN