When people usually say that markets aren't efficient, they don't mean that optimal resource allocation is a computationally intractable problem. They're saying that they see, clear as day, obvious inefficiencies that aren't being corrected. They're saying that there are easily noticeable inefficiencies that aren't being corrected. And finding easily noticeable inefficiencies isn't NP-hard, by definition of easily noticeable.
A better version of the efficient market hypothesis would be that markets are inexploitable. There is no easy action I can take that corrects a market inefficiency and makes me money. This is the version that comes up in cocktail party conversations and it's also the one that Dan Luu is talking about. "If XXX is systemically undervalued by the market, why can't I start a company that specialises in using XXX?" The discussion following this question is much more relevant and interesting than encoding 3SAT into economic models.
No, that's absolutely not true and relies on what I think is the most perniciously false assumption behind market economics: that all market participants only make moves within the market itself.
If you're trying to win at chess then learning to master the rules and strategy of chess is where you focus your attention. But if you're trying to defeat your opponent (or not get defeated by them), you'll probably do better to bring a gun and/or body armor. If you focus 100% of your attention on the chessboard, you are completely opening yourself up for exploitation by an opponent who is willing to play the metagame.
And, indeed, in market economics, actors invariably do play the metagame. This is why we get cabals, trusts, rent seeking, regulatory capture, monopolies, price fixing, price dumping, lobbying, etc.
The ultimate goal of market actors is not to be maximally efficient. It's not even to win the market game. It's to make the most money. And often the best way to make the most money is to rig the game, cheat, or get the rules changed in your favor.
A book on "chess strategy" would be very different if it's definition of "chess" included the whole of human conflict and warfare. It probably wouldn't spend much time talking about rooks and pawns at all.
As I said, there is no reason those efficiencies should be easily correctable - because markets aren't efficient! That's the whole point. It's only in an efficient market that they would be correctable. This is the same as lots of computational and other problems. Lots of instances are easy and heuristics can often work very well. But you will still come up with situations where obviously broken things happen and are hard to make algorithms work.
It's sort of like having a cocktail party conversation about why you can't exceed the speed of light. Except because it's economics, you get stuck because there often isn't any real rigor behind it that you can push on. Just the empirical. Which I get why it's fun to talk about (really!) - without any meaningful rigor, anyone can participate and have fun - got a crazy empirical story? Awesome, that's all you need to prove something in economics! It makes for fun discussions where most people can participate and feel like it's not too hard.
I have no issue with that - my issue is of course that the cocktail party is not distinguishable from the field ;)
Beyond that, arguing they are inexploitable/unpredictable seems equivalent to whether they are efficient (and in most papers is considered equivalent to the efficiency hypothesis). I'm really unsure how you are trying to distinguish it. Maybe you could formulate it for real and show how it is not equivalent to the efficiency question?
Hard to deflate asset-price bubbles are a fact of finance.
For strong form efficiency (which requires markets perfectly reflect all available information) - You would have trouble finding people who still believe in strong form efficiency. The weak form paper above cites several papers that go into why strong form efficiency is impossible. There are formal proof versions around. In practice, even empirical studies of strong form efficiency haven't supported it either - it's just very easy to find practical counterexamples.
But this assumes that brute force is the only possible way to find a winning strategy, and thus proves far too much. A similar argument would prove that sorting is NP hard, if you start by the assumption that the only way to sort data is by trying every possible permutation.
I may be wrong, but I'm pretty sure any time you claim to have a proof that a problem is NP complete, but your proof doesn't include a reduction, you're doing it wrong.
(The paper does offer what it calls a reduction to 3-sat , but it's completely hand-wavy, and I can't even understand the intuition behind it at all.)
The underlying thesis being that market success is orthogonal to your internal company's state, inefficiencies included.
Also, more specifically - as a Samsung user for my preferences they offer as good or better products than Apple while operating on a smaller budget.
There is not really a strong need to go into why inefficiencies can persist, etc, because at a baseline, it turns out there is no provable theory that markets should be efficient at all.
Instead, we have the sort of equivalent of Galileo - people really badly want markets to be efficient. They feel like they should be, because intuitively, it seems like it should work that way (much in the "god does not play dice" sense). People who suggest they aren't, even when math backs them up, are ridiculed. Eventually, as Max Planck said, science will advance funeral by funeral, and we'll stop pretending markets should be efficient based on "the efficient market hypothesis". Or we'll discover P=NP! Which would be much cooler.