4 ms·
> (a) we often don’t care about an exact solution If we're trying to prove np-hardness we do.
by bawolff 6y ago
> (a) we often don’t care about an exact solution
If we're trying to prove np-hardness we do.
- LolWolf 6y agoIt doesn’t really make sense in this case though, does it? One example is that Knapsack can be approximately solved in polynomial time for all tolerances eps (I.e., it has a Fully-polynomial time approximation scheme, or FPTAS). The EMH is only talking about essentially approximate behavior (as the paper also mentions, with repeated experiments).
- bawolff 6y agoWhich is why this whole venture is more an exercise in pendantry rather than an actual attempt to solve np problems with markets.