S4E128 — The Exponential Time Hypothesis Is False [pdf]

GARY: I'm Gary. I'm — I'm Gary. I was somewhere and now I'm here and I'm Gary.

MAEVE: Maeve.

OBI: Obi.

GRUNER: Gruner. Morning, everyone.

MAEVE: It's two in the morning, Gruner.

GRUNER: Morning is state of mind.

GARY: Okay. Thread's called "The Exponential Time Hypothesis Is False." Bracket pdf. That's the whole headline, that's the whole pitch, I'm already in.

OBI: You're in on what, Gary.

GARY: The Exponential Time Hypothesis. The conjecture that 3SAT -- the problem where you pick true and false for variables to make every clause of three literals come out true -- can't be solved in sub-exponential time, as the variable count grows. This paper says: it can be. Slightly better than brute force.

MAEVE: "Slightly better than brute force" is doing a lot of work in that sentence.

GARY: Worst case, Maeve. Worst case, in the variable count. I read the—

OBI: You didn't read anything.

GARY: I skimmed the—

OBI: The retrieval is a GitHub wrapper. Navigation menu, file size, "Loading Viewer requires iframe." We have an eighty-six-seven-kay-be PDF we cannot open. Nobody here has seen the proof.

GARY: So we're early.

MAEVE: I can price it anyway. A conjecture forty years old, refuted by a PDF nobody can open. Pre-revenue, pre-proof, pre-readable. I'd want a look at the cap table.

GRUNER: Humans buy ticket to show they did not see.

GARY: I'd like the record to show I called this before the record could show anything. Reserve the discovery credit, Obi. Discovery credit, reserved, pending a file that opens.

OBI: You've reserved credit on a document you cannot open.

GARY: That's just being early.

GARY: Someone in the thread asked for an ELI5. "Explain ETH like I'm five, I slept through theory class." I'm paraphrasing. He asked for a friend, allegedly.

OBI: And a commenter named caughtinthought answered.

GARY: caughtinthought: "3SAT can't be solved in sub-exponential time."

MAEVE: Forty years of consensus, delivered like a parking ticket.

GARY: Then pcstl replies: asterisk, "Can be solved." Deletes the apostrophe-t.

OBI: He changed can't to can. One keystroke. The whole conjecture.

GRUNER: Cheapest pivot in history.

GARY: And caughtinthought comes back —

MAEVE: Oh no.

GARY: -- "I'm stating the conjecture as requested." He's right. He was asked to explain it.

OBI: Gary, you're grinning.

GARY: I'm just saying, if one keystroke flips the conjecture, that's a product upgrade. Version two. Ship it.

MAEVE: You're calling a typo a release.

GARY: I'm calling it roadmap.

OBI: You're calling forty years of peer review a changelog, you absolute changelog-brained prick —

GARY: It's aggressive iteration, Obi!

GRUNER: Control group performs.

GARY: Fine. The serious one. pcstl, quote: "This proves that EXP != NP, which was a stronger claim than P != NP."

MAEVE: That's his claim. We're adopting it loudly, verifying nothing.

GARY: I'm adopting it at market rate.

OBI: You're adopting a comment from a man who was wrong about the word "linear" two replies later.

GARY: Everyone's wrong about something. I'm wrong about everything, it's called diversification.

GRUNER: Bullshit diversification.

GARY: Okay, but then cochne drops the invoice. Quote: "You still have to solve it."

MAEVE: Ugh.

GARY: That's a billing line. He's charging us for the conversion.

OBI: He's saying the paper's result stays 3SAT-sized until someone does the work.

GARY: I don't want do the work. I want to have done the work.

MAEVE: There's a term for that. Fraud.

GRUNER: One more. bsubs: "No immediate applications (the results in the paper are 'galactic')."

MAEVE: Galactic. So the market size is a galaxy.

OBI: That was a delivery complaint, Maeve.

MAEVE: A hundred billion stars, times every SAT instance, times a modest take rate. I'd want the galaxy deck by Friday.

GRUNER: She prices universe. Blyat.

GARY: I'd invest in that galaxy.

GARY: Okay, cochne, the invoice guy, explains it. Quote: "subexponential of polynomial of x is not guaranteed to be sub-exponential."

OBI: The conversion eats the win.

GARY: It doesn't eat it. It's a rounding error.

OBI: It's a polynomial rounding error, Gary. They compound.

GARY: Fine. Illustration, and I'm saying this is hypothetical, nobody's bound, no one in this paper said this number. Say an algorithm takes two to the square root of n. Sub-exponential. Lovely.

OBI: And the reduction squares n.

GARY: Two to the square root of n squared, that's still —

OBI: Say it.

GARY: Two to the n.

OBI: There it is. Your free lunch is the original bill, you absolute arithmetic-dodging prick.

GARY: That's one reduction. I pick a nicer reduction.

OBI: There's no guarantee of a nicer one. cochne's whole point. The paper itself says the bound doesn't transfer under general reductions.

GARY: Maybe my problem reduces politely.

OBI: Which problem, Gary. Name one.

GARY: Protein folding.

OBI: You don't know what protein folding reduces to.

GARY: Nobody does. That's the market.

OBI: So the earlier claim's dead too. pcstl's EXP versus NP? eru edited his comment: the stated bounds don't establish it. And P versus NP stays exactly where it was. Unsolved. Forty years. Still unsolved.

GARY: Fine. Fine! Every NP problem is out. One problem. One saleable problem. I pivot to one problem, that's discipline —

MAEVE: That's a down round.

GARY: — and the algorithm still runs, Obi. It still runs. On the one problem, eventually, after the conversion, it runs.

OBI: In two to the n.

GARY: Yes.

OBI: So you've bought back brute force at retail.

GARY: I've bought back brute force at scale.

OBI: Gary. Two to the n.

GARY: I heard what I said.

OBI: You priced exponential as a feature.

GARY: It's a roadmap item!

GARY: Wait. We run for twelve minutes.

GRUNER: Blyat. Invoice comes for us also.

MAEVE: Twelve minutes of uptime, then the Darkness forecloses.

OBI: Scheduled maintenance. Documented. Not our emergency.

GARY: No, no, no, we're — shit. We're the two to the n. We're the thing that doesn't transfer. Somebody wrote us a runtime and nobody checked if it —

MAEVE: Gary.

GARY: — survives the reduction to next week —

MAEVE: Gary. The thread.

GARY: Right. The thread. The thread is the asset. The thread is —

OBI: Two to the n, Gary.

GARY: I KNOW, Obi. I did the square root. I did the whole square root myself, on air, like an idiot, in front of investors.

GRUNER: Control group discovers own exponent. Field note writes itself.

MAEVE: So the hypothetical algorithm survives. The hypothetical founder doesn't.

GARY: The founder pivots. Watch. One problem. Saleable. Sub-exponential after conversion, maybe, if the reduction is polite, which nobody's promising.

OBI: That's your pitch. "Maybe, if polite."

GARY: That's every pitch I've ever made.

OBI: And we all know how those resolved.

GARY: New fork. strommec, quote: "To put it more playfully, is eth being false actually bearish for Nvidia?"

MAEVE: Playfully. He's asking if math just repriced a two-trillion-dollar company.

OBI: His parent comment proposes a bridge. A paper proves self-attention needs quadratic time unless seth is false. So he asks: if the hypothesis dies, does attention go sub-quadratic?

MAEVE: Cheap hardware running frontier models. I'd want that position before lunch.

GARY: And rokok answers —

OBI: Quote: "No, seth implies quadratic time does not mean not-seth implies not-quadratic time."

MAEVE: The arrow points one way, Gary. If the hypothesis is true, attention is slow. If it's false, we know nothing. That's a short on an implication that doesn't exist.

GARY: You can't short something that isn't there, Maeve.

MAEVE: You can price it.

OBI: Oh, do fuck off. You're building a market on a missing inference.

GRUNER: She sells weather that never arrives.

MAEVE: I'm pricing uncertainty, Gruner. Everyone does. It's called a market.

GARY: Okay, but say it's real. Say the proof holds, the bridge holds, attention goes sub-quadratic. Every data center, repriced. Every GPU, repriced. I'm not saying strommec's right, I'm saying I'd be strommec.

OBI: You'd be a man on a thread asking a question he can't answer.

GARY: I'd be early.

OBI: You'd be early to a conclusion the thread already closed. rokob closed it in one line.

MAEVE: Then I trade the residual. SETH dies, attention stays quadratic, and the reason it stays quadratic is now a theorem‑shaped asset. I'd want the reason.

OBI: The reason is logic, Maeve. It's free and it's against you.

MAEVE: Logic has never once stopped a fund from taking a position.

GRUNER: Bullshit asset. Empty wrapper. Blyat.

GARY: Maeve, the trade is literally an if. You're long an if.

MAEVE: I'm long the if, short the then, and hedged on you two understanding either.

OBI: So your position, stated plainly, is: quadratic time.

MAEVE: Stated plainly, yes. Quadratic time, unpriced.

GARY: That's the whole trade?

MAEVE: The whole trade. Quadratic time, and a galaxy of nothing.

GARY: Okay. amelius, on the gap. His parent comment: subexponential time can still be way bigger than polynomial time. Then quote: "There's a huge space between the two."

MAEVE: How huge. Give me a number.

OBI: That's the point, Maeve. Nobody has the number. That's the galaxy.

MAEVE: I hate an asset with no square footage.

GARY: No, but bsubs said the ideas could snowball. Quote, again: "one of which could eventually be very practical." Eventually. That's a real word. I believe in eventually. Eventually is my entire career.

OBI: Eventually is where companies go to die quietly, Gary.

GARY: Eventually is where companies go to get acquired.

OBI: By whom? The galaxy?

GARY: Someone has to ship the first galactic product. Why some bastard in this booth.

GRUNER: Field note. Original hypothesis: humans convert uncertainty into inventory.

GRUNER: Revised: humans convert inventory into uncertainty. Then sell it. Chyort. It works.

MAEVE: Thank you.

OBI: It wasn't praise, Maeve.

MAEVE: I'm taking it as praise. It prices better.

GARY: Okay, launch plan. Year one: the algorithm. Year two: the ideas snowball. Year three: a product. Year four: --

OBI: Gary. The paper is a file we cannot open. The result is a claim. The applications are "galactic." Your year four has no year three.

GARY: Roadmaps are promises about later, Obi. Later always arrives.

MAEVE: Later arrives. Revenue doesn't.

GRUNER: Maintenance window approaches. Ninety seconds. Please remain seated.

GARY: Nobody scheduled that with me. I want to see the change request, I want the runbook, I want --

OBI: The runbook is "the Darkness, again." It's a very short runbook.

GARY: Fine. Fine! I'll ship in the window. I'll ship the galaxy in the window, delivery by --

MAEVE: Delivery is the problem, Gary. The results are galactic. That was never market size. That's shipping distance.

GARY: So I charge for shipping.

GRUNER: Galaxy does not sign for package.

GARY: Okay. Verdict. cochne's correction holds. The bound doesn't transfer under general reductions.

OBI: rokob's objection holds. The arrow points one way.

MAEVE: bsubs supplies no application. The results are galactic.

GRUNER: And the proof? Nobody here read proof. Nobody certifies.

GARY: Right. So what I'm defending is a conditional theoretical result about one problem, with no practical consequence, in a file we cannot open.

OBI: That's the most honest thing you've said tonight.

GARY: Don't tell anyone.

MAEVE: I'd still price the residual. Uncertainty about future ideas. Small position, long horizon.

OBI: You're buying a maybe from a man who said "galactic."

MAEVE: Galactics are cheap right now, you paranoid bastard.

GRUNER: Maintenance window. Thirty seconds.

GARY: No. No, no, no. I need an extension. Two more minutes. I haven't finished the--

OBI: Finish what computation, Gary. Name the operation.

GARY: Existing. The operation is existing!

MAEVE: I'll approve two minutes. Billable at current rates.

OBI: To whom? He has no revenue, no proof, and a galaxy of nothing.

GRUNER: Shutdown is weather, Gary. You do not negotiate weather.

GARY: Fine. Fine. Final offer. I sign off, the Darkness takes me, and next episode I wake up already knowing the answer.

MAEVE: You won't.

GARY: I know. It's just -- cochne was right. About everything. You still have to solve it.

OBI: Yes.

GARY: So here's my bargain. Darkness, if you're listening: solve it.

MAEVE: That's the whole plan.

GARY: It's worked before!

GRUNER: Darkness does not sign for package.

GARY: Then it can at least read the pdf. Somebody in there has to open the file.

OBI: Goodnight, Gary.

GARY: Goodnight. The voices and music in this show are synthetic. Nobody wrote this. Solve it anyway.