4 ms·

NP hard problems get abused for justifying things they cannot. An NP hard problem, even if it cannot be approximated does not mean the average input cannot be

NP hard problems get abused for justifying things they cannot. An NP hard problem, even if it cannot be approximated does not mean the average input cannot be solved efficiently. Examples: - An NP hard problem is not sufficient for building crypto. - Type solving for many programming languages is EXP TIME complete, yet those languages prosper and compile just fine. Beware the idea of taking a mathematical concept and proof and inducing from it to the world outside the model.

DiggyJohnson 5y ago
First of all I do see that you called it an example; I don't think you're straw-manning or anything: I think using chaos theory / Bayesian concepts is a significantly better metaphor for "life as we experience it" than it is for the examples you gave.
nostrademons 5y ago
And human beings make approximate solutions for the average input all the time. That's what gut feelings, instincts, heuristics, and motivated reasoning are, along with all the other shortcuts we take to function in daily life. The article is asking why it's so hard to be rational though, i.e. follow a logically-valid set of inferences forward to an unambiguous conclusion. Assuming one of your premises is that correct rationality implies reasoning statistically about a network of interrelated beliefs, the uncomputability of a Bayesian net is relevant to that.
- munk-a 5y ago
  Following a fully logically valid set of inferences seems extremely inefficient - we need to make decisions constantly and relying on short hand for most of those seems perfectly rational - it's rational to trust irrational gut feelings for most unimportant decisions because trying to fully prove all actions is a fool's errand. I think the article is more focused on those big decisions where rationality is certainly warranted and so often ignored. People who are highly skilled at life have developed their gut feelings and instincts to be able to determine which decisions they really need to sit down and think hard about and which ones they can mostly ignore. When most people buy their first house the decision is so immensely large and represents such a high value (more than half a million at least for a lot of city folk) that there is a desire to detach from it to free yourself from responsibility - since you cannot sanely account for all factors it is "safer" to protect your ego by delegating the decision entirely on your id - doing so allows you to, post de facto, entirely free yourself from any responsibility of your poor decision. This, I think, is the main factor we need to fight against to make rational decisions - you must accept failure and be willing to be wrong without shame. Do your best to evaluate your options on important decisions and realize that there are a number of decisions you obviously can't fully rationalize out - you can only make your best attempt. But realize that making your best attempt and being wrong - as much as it might hurt your ego - is a better alternative than "letting it ride" and being able to stand blameless on the far end. The fight for rationality is mostly a fight against emotional fragility and intellectual laziness.
strulovich 5y ago
Also, adding on my previous comment, for an interesting take on the limitations of NP hard applicability to real life problems see Parameterized Complexity: https://en.wikipedia.org/wiki/Parameterized_complexity https://en.wikipedia.org/wiki/Parameterized_complexity
User23 5y ago
Similarly even mediocre programmers do a pretty good job writing programs that halt.
amelius 5y ago
Ok, so what is the class of problems that is hard for any input?
- MichaelZuo 5y ago
  Reducing entropy.
  - amelius 5y ago
    Only in closed systems.
btilly 5y ago
You are correct. For example the worst and average cases for the Simplex Method are dramatically different. However, in practice, complex Bayesian nets do wind up being computationally intractable. Therefore attempts to build real world machine learning systems consistently find themselves going to computationally tractable heuristic methods with rather obvious failure modes.
morpheos137 5y ago
One thing I notice these days on line is people overgeneralise about everything (irony intended).

DiggyJohnson 5y ago

First of all I do see that you called it an example; I don't think you're straw-manning or anything: I think using chaos theory / Bayesian concepts is a significantly better metaphor for "life as we experience it" than it is for the examples you gave.

nostrademons 5y ago

And human beings make approximate solutions for the average input all the time. That's what gut feelings, instincts, heuristics, and motivated reasoning are, along with all the other shortcuts we take to function in daily life. The article is asking why it's so hard to be rational though, i.e. follow a logically-valid set of inferences forward to an unambiguous conclusion. Assuming one of your premises is that correct rationality implies reasoning statistically about a network of interrelated beliefs, the uncomputability of a Bayesian net is relevant to that.

munk-a 5y ago
Following a fully logically valid set of inferences seems extremely inefficient - we need to make decisions constantly and relying on short hand for most of those seems perfectly rational - it's rational to trust irrational gut feelings for most unimportant decisions because trying to fully prove all actions is a fool's errand. I think the article is more focused on those big decisions where rationality is certainly warranted and so often ignored. People who are highly skilled at life have developed their gut feelings and instincts to be able to determine which decisions they really need to sit down and think hard about and which ones they can mostly ignore. When most people buy their first house the decision is so immensely large and represents such a high value (more than half a million at least for a lot of city folk) that there is a desire to detach from it to free yourself from responsibility - since you cannot sanely account for all factors it is "safer" to protect your ego by delegating the decision entirely on your id - doing so allows you to, post de facto, entirely free yourself from any responsibility of your poor decision. This, I think, is the main factor we need to fight against to make rational decisions - you must accept failure and be willing to be wrong without shame. Do your best to evaluate your options on important decisions and realize that there are a number of decisions you obviously can't fully rationalize out - you can only make your best attempt. But realize that making your best attempt and being wrong - as much as it might hurt your ego - is a better alternative than "letting it ride" and being able to stand blameless on the far end. The fight for rationality is mostly a fight against emotional fragility and intellectual laziness.

strulovich 5y ago

Also, adding on my previous comment, for an interesting take on the limitations of NP hard applicability to real life problems see Parameterized Complexity: https://en.wikipedia.org/wiki/Parameterized_complexity https://en.wikipedia.org/wiki/Parameterized_complexity

User23 5y ago

Similarly even mediocre programmers do a pretty good job writing programs that halt.

amelius 5y ago

Ok, so what is the class of problems that is hard for any input?

MichaelZuo 5y ago
Reducing entropy.
- amelius 5y ago
  Only in closed systems.

btilly 5y ago

You are correct. For example the worst and average cases for the Simplex Method are dramatically different. However, in practice, complex Bayesian nets do wind up being computationally intractable. Therefore attempts to build real world machine learning systems consistently find themselves going to computationally tractable heuristic methods with rather obvious failure modes.

morpheos137 5y ago

One thing I notice these days on line is people overgeneralise about everything (irony intended).