3 ms·

In my experience, solving the NP-hard problem isn't the part that is hard, it's reducing the problem space and/or solution space to make it into a P-problem (wh

In my experience, solving the NP-hard problem isn't the part that is hard, it's reducing the problem space and/or solution space to make it into a P-problem (when n is sufficiently big enough to worry about it). For example, changing how you're storing the data in the first place, or talking to PM/PO's to learn if you really need an exact solution or if a very close approximation is ok. Sometimes, you're even trying to solve this problem while n has grown over months or years, and some customers are hitting the tipping point and the app is crashing. So there's a lot of pressure to perform. That's what makes np-hard problems hard, imho; not the problem itself, but all the bullshit to get rid of it.

imtringued 3y ago
Computing a competitive equilibrium is NP-hard in Fisher Markets. [0] The economy is not controlled by some grand central institution calculating competitive equilibria. We have independent humans with some institutional soft constraints optimistically buying and selling things. Even if we assume that there is no information asymmetry and all preferences are known, everyone has to run the algorithm themselves in their head and everyone has to arrive at the same competitive equilibrium. That is what it takes to guarantee a competitive equilibrium. The thing is, if you have anything less than the competitive equilibrium, you lose the property of "free market supremacy" aka that markets are superior in every situation and that government intervention can never make anything better. So the NP hard problem has to be solved, you can't wiggle yourself out of this with an approximating solution. Any x%-approximation leaves a 100%-x% gap for something else to replace the free market. We now arrive in reality, where sometimes markets are really good and sometimes they are really bad, but that has not stopped people from worshipping Ayn Rand. The very same Ayn Rand that needed medical services provided by the government and therefore landed in the 100%-x% gap where markets aren't so nice any more. The by far dumbest part though, is that the economy in reality is an iterative process, not a static process that jumps from one competitive equilibrium to the next, and there are ways to use local rules and institutions to encourage arriving as close to equilibrium as possible but those are considered government intervention or against human nature or some other nonsense, even if they actually let markets be more "free" and with less government intervention overall. So you have these schizophrenic economists who argue in favor of unattainable competitive equilibria, while simultaneously sabotaging the arrival at close enough equilibria plus some government intervention as a fallback. The height of irony is that this results in the economy ending up in a strong disequilibrium, but disequilibrium is fine as long as the economy is growing. The moment growth stops, that disequilibrium will become more and more apparent over time. [0] https://en.wikipedia.org/wiki/Fisher_market#Fisher_markets_with_indivisible_items https://en.wikipedia.org/wiki/Fisher_market#Fisher_markets_w...
- withinboredom 3y ago
  In my experience, every NP-hard problem I've run into was due to trying to solve it naively or "up-front" and can be reduced into something not-so-by-the-book which usually involves storing the data in a different form, or reducing scope (i.e., ignoring impossible solutions/values). I've yet to see a real-world NP-hard problem that can't be solved this way; but would never be accepted scientifically because they don't solve it in the 'general case.'
  - adrianN 3y ago
    I guess you never tried to find optimal join orders for you sql engine.
    - withinboredom 3y ago
      I actually have :), it was a time travelling database for $work. In our case, we assumed that queries wouldn't change too much (applications running on them tend to query the same tables over and over again). Thus we just picked an order "at random" (though IIRC, there were some heuristics) for table-sets, otherwise we used the best performing one seen so far -- but it would randomly run another query with a different order to keep finding the best one. We just didn't care about trying to solve it 'up-front' and were more interested in empirically choosing the best solution.
      - adrianN 3y ago
        A random search like that might give okay results but has no guarantees approximation ratio.

imtringued 3y ago

Computing a competitive equilibrium is NP-hard in Fisher Markets. [0] The economy is not controlled by some grand central institution calculating competitive equilibria. We have independent humans with some institutional soft constraints optimistically buying and selling things. Even if we assume that there is no information asymmetry and all preferences are known, everyone has to run the algorithm themselves in their head and everyone has to arrive at the same competitive equilibrium. That is what it takes to guarantee a competitive equilibrium. The thing is, if you have anything less than the competitive equilibrium, you lose the property of "free market supremacy" aka that markets are superior in every situation and that government intervention can never make anything better. So the NP hard problem has to be solved, you can't wiggle yourself out of this with an approximating solution. Any x%-approximation leaves a 100%-x% gap for something else to replace the free market. We now arrive in reality, where sometimes markets are really good and sometimes they are really bad, but that has not stopped people from worshipping Ayn Rand. The very same Ayn Rand that needed medical services provided by the government and therefore landed in the 100%-x% gap where markets aren't so nice any more. The by far dumbest part though, is that the economy in reality is an iterative process, not a static process that jumps from one competitive equilibrium to the next, and there are ways to use local rules and institutions to encourage arriving as close to equilibrium as possible but those are considered government intervention or against human nature or some other nonsense, even if they actually let markets be more "free" and with less government intervention overall. So you have these schizophrenic economists who argue in favor of unattainable competitive equilibria, while simultaneously sabotaging the arrival at close enough equilibria plus some government intervention as a fallback. The height of irony is that this results in the economy ending up in a strong disequilibrium, but disequilibrium is fine as long as the economy is growing. The moment growth stops, that disequilibrium will become more and more apparent over time. [0] https://en.wikipedia.org/wiki/Fisher_market#Fisher_markets_with_indivisible_items https://en.wikipedia.org/wiki/Fisher_market#Fisher_markets_w...

withinboredom 3y ago
In my experience, every NP-hard problem I've run into was due to trying to solve it naively or "up-front" and can be reduced into something not-so-by-the-book which usually involves storing the data in a different form, or reducing scope (i.e., ignoring impossible solutions/values). I've yet to see a real-world NP-hard problem that can't be solved this way; but would never be accepted scientifically because they don't solve it in the 'general case.'
- adrianN 3y ago
  I guess you never tried to find optimal join orders for you sql engine.
  - withinboredom 3y ago
    I actually have :), it was a time travelling database for $work. In our case, we assumed that queries wouldn't change too much (applications running on them tend to query the same tables over and over again). Thus we just picked an order "at random" (though IIRC, there were some heuristics) for table-sets, otherwise we used the best performing one seen so far -- but it would randomly run another query with a different order to keep finding the best one. We just didn't care about trying to solve it 'up-front' and were more interested in empirically choosing the best solution.
    - adrianN 3y ago
      A random search like that might give okay results but has no guarantees approximation ratio.