Sure, sure, you can encode difficult computational problems into markets in convoluted ways, but this is uninteresting unless you're into that kind of thing.
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.