8 ms·
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:/
by chaboud 8y ago
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://citeseerx.ist.psu.edu/viewdoc/download%3Fdoi%3D10.1.1.78.6237%26rep%3Drep1%26type%3Dpdf&ved=2ahUKEwjg3oON9p7gAhXiHDQIHctEBfEQFjAAegQIAxAB&usg=AOvVaw3KFPsAt9iWqBpUqZrEigpu&cshid=1549174909564 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 as, effectively, a lower bound for ML problems (because, otherwise, why are you even ML'ing the thing?), whether or not a problem is "learnable" is, unsurprisingly, probably NP-Hard. Aggregability and learnability look staggeringly similar to me.
Demonstrating otherwise would be a huge result. Writing a paper confirming Kreinovich and Shpak in a slightly different domain is basically a "Water is Wet" paper.
Having not yet read the paper, I'm unaware of any new ground here.
- foxrob92 8y agoI mean, haven't the authors shown that the problem is "worse" than NP-hard? They have shown it to be undecidable?
- diegoperini 8y agoHow is worse than NP-hard named in the field? NP-impossible? Disclaimer: I'm really noob, not asking it sarcastically.
- fspeech 8y agoUndecidable means there is no logical way to have an answer. Turing’s halting problem is one such.
- vinceguidry 8y agoThere'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.
- fspeech 8y ago“It's just impossible to write a general-purpose algorithm to solve it in all cases.” That is the definition of an undecidable problem. Independence, as in Euclid’s fifth postulate, is not what we typically think of as undecidability, though can be referred to as such.
- betterunix2 8y agoThat is incorrect. The halting problem can be answered -- every Turing Machine either halts or does not halt on a given input. Undecidable only means that we cannot have a single algorithm that outputs the correct answer in every case.
- fspeech 8y agoThis is the first paragraph from the Wikipedia article on undecidable problems: “In computability theory and computational complexity theory, an undecidable problem is a decision problem for which it is proved to be impossible to construct an algorithm that always leads to a correct yes-or-no answer. The halting problem is an example: there is no algorithm that correctly determines whether arbitrary programs eventually halt when run.” https://en.m.wikipedia.org/wiki/Undecidable_problem https://en.m.wikipedia.org/wiki/Undecidable_problem
- adrianN 8y agoThere are an infinite number of complexity classes that are (probably) harder than NP. Popular ones include PSPACE and EXPTIME. You might want to google for "polynomial hierachy".
- foxrob92 8y agoNP-hard problems can be solved. The Continuum Hypothesis [0] (which the authors are saying the learning problem is isomorphic [1] to) is not provable from the axioms of set theory. You can add "The Continuum Hypothesis is true" OR "The Continuum Hypothesis is false" to the axioms, and still have consistent mathematics. [0] Continuum hypothesis is that the set of Integers (0, -1, 1, -2, 2, ...) is infinite but smaller than the set of Reals (Integers + Rationals + Irrationals), and there are no infinite sets with size smaller than the Reals, but larger than the Integers. [1] not sure of correct term here - the point is that they have shown the problems are the same.
- niklasd 8y agoI'm not sure what you mean with "can be solved", but I would spell it out a bit different: There are NP-hard problems that are undecidable, that means, there is no algorithm that can decide the question for every input. However, in some instances we are able to solve these problems (even quite easy). For example we know that an algorithm like "while TRUE DO (nothing) END" will never terminate, even though the halting problem is undecidable. However, if a NP-hard problem is also in NP, than it can be solvend. But it will take exponential time in the worst case. That, too, does not mean that in some instance we are able to solve them in reasonable time.
- betterunix2 8y agoThis is wrong. NP-hard problems can be solved, they just appear to hard to solve efficiently. NP-hard problems are always decidable, like everything in polynomial hierarchy (P, NP, co-NP, and higher classes that have oracle access to lower classes). Undecidable problems e.g. the Halting problem cannot generally be solved using an algorithm (so it has to be solved on a case-by-case basis and requires "creativity").
- niklasd 8y agoSorry, but you are flat out wrong. For example, the halting problem is NP-hard and undecidable [1] I think you might confuse NP-hard with NP-complete. There are problems that are NP-hard, not in NP and unsolvable. If a problem is NP-hard _and_ in NP, then they can always be solved. [1] https://en.wikipedia.org/wiki/NP-hardness https://en.wikipedia.org/wiki/NP-hardness
- betterunix2 8y agoPSPACE-complete is an example. EXPSPACE is another.
- threatofrain 8y agoAren't some undecidable problems "better" with regards to practical needs because we can achieve arbitrarily precise results more cheaply?
- Cacti 8y agoNP-hard and undecidability are completely different things. They’re barely on the same planet.
- miclill 8y agoI would argue that for practitioners it is the same planet. But I agree that they are not the same thing.
- shoo 8y agodisagree, 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.
- pfortuny 8y agoWell: 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.
- adrianN 8y agoThat strongly depends on the practitioner and the problem. We solve (or approximate) NP hard problems all the time. SAT solvers are really good, so are ILP solvers and a host of other tools that solve a ton of instances of NP-complete problems that arise in practice. If you're into software verification, people solve undecidable problems there every day. Complexity results are always worst-case results. In practice you can often solve all instances you actually care about.
- 8y ago
- raverbashing 8y agoAn NP-hard problem is still possible to be solved. Impractical but possible. An undecideable solution cannot be proven true.
- pfortuny 8y agoYes 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”).
- pas 8y agoAre there any at all? If you have exact numbers you can decide in finite time. Always, if I'm not mistaken. So, unless there is an infinity encoded in the exact problem somehow, you can always solve it by simple brute force enumeration. Look at the busy beaver, it's completely possible theoretically to simply enumerate all the possible states of a tape for a given N, and play the corresponding Turing machines. Even if calculating this is physically impossible, and proven to be impossible to generalize for any N. (That is the BB functions are uncomputable, but of course not exact values.)
- pfortuny 8y agoGödel’s sentence comes to mind. Yes, it is not “practical” but it is undecidable.
- pas 8y agoGodel's sentence is not an exact problem. It's a big number representing a claim (a theorem) about Godel numbers and the sentence itself. There's nothing to calculate there. It's a proof by construction for Godel's incompleteness theorem.
- threatofrain 8y agoA non-computable problem might still be practically "better" because its solution might be approximated precisely and more cheaply, such as the approximation of a real number.
- zodiac 8y agoIf you didn't read the paper, at least read the title: "unsolvable" does not mean NP hard
- chaboud 8y agoI did read the paper (now). Their question is of “learnability”, which relates to aggregability/compressibility and dimensionality. This stuff is all in the same ballpark. Having read their paper, I do appreciate the formulation and approach. I just don’t find the result “surprising” in the slightest.