NP-hard does not mean hard (2017)

Sure, but in practice that’s not what people worry about, from what I have seen. At least when dealing with SMT problems, the SAT part is the easy part.

Isn't there some graph problem about finding cliques that is NP-hard (presumably NP-complete in the decision version) but that has an expected _constant_ time algorithm over the usual distribution of random graphs?

I seem to remember the algorithm is something like "check a few samples at random, if that doesn't find what you're after then do exponential-time search" and the point is the chance that the samples don't find what you're after is exponentially small, because the thing you're looking for is so frequent.

If you're allowing for some error probability, then the answer is trivially yes. For example, the NP-Complete problem of "does this graph have a clique of size sqrt(n)" is trivial over G(n, 1/2) random graphs, because the answer is No with overwhelming probability (something decaying exponentially in n or n^2). So you don't have to read the input before responding.

If you're referring to Las Vegas style (always correct) algorithms, then I don't think something along those lines can work. Reading a constant number t bits from a G(n,p) random graph yields each possible event with the constant probability (1/2)^t. So the expected running time is still at least some (small) constant times that of the failure case, which is still exponential.

Are you perhaps thinking of the average case problem Planted Clique, where the task is to distinguish between a "clean" random graph G(n, 1/2) and a "planted" one where we force some random set of, say, k=n^(1/3) vertices to induce a clique? While distinguishing a graph with a k-clique from one without one is NP-hard on general graphs, you can show that G(n, 1/2) graphs virtually never contain cliques as large as 3 log n, and hence brute force searching all 3 log n sized subsets of vertices for cliques (in subexponential time n^(3 log n)) will almost always lead you to the correct answer. And once you find a clique of size 3 log n, expanding it to n^(1/3) can be done quickly using a greedy algorithm.

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_w...

That's an exaggeration. It's pretty safe to assume P ≠ NP, in practice. In theory you'd have to be more careful, but people have relied on weaker assumptions in math proofs. But for statements about super-mario, it's more than reasonable to assume.