The disproof of the Exponential Time Hypothesis

In my last post, I talked about the Exponential Time Hypothesis (ETH), and how it applies to puzzles. Here I’m going to roughly outline the disproof of the hypothesis.

I’m following a graduate level lecture by Ryan O’Donnel, with additional background reading. More specifically, I’m following the first half of the lecture, because I gave up on understanding or explaining the rest.  My goal is to convey a broad conceptual understanding, and flavor.

Puzzles inside other puzzles

Have you ever heard of people creating working computers inside Minecraft? Have you heard that Magic: The Gathering is Turing complete? Some game systems are complex enough that in principle, you can program anything inside of them, including another game. And so, you can program Minecraft inside Minecraft (link to video).

Puzzles are like this as well. You can program puzzles inside of other puzzles. You can make a sokoban puzzle whose solution is equivalent to solving a sudoku. And then you can make an origami crease pattern, where figuring out how to fold it is equivalent to solving a sokoban. I mean, you could do it in principle, although it would be horribly inefficient in practice.

[Read more…]

The Exponential Time Hypothesis in puzzles

The Exponential Time Hypothesis (ETH) is a conjecture in computational complexity theory. One inexact way of stating the ETH is, “Some puzzles require brute force to solve.” I think the ETH is intuitively true, to the extent that I have asserted it on this blog without naming it.

So I was shocked to learn that ETH is false. It was recently disproven by LLMs from OpenAI and Anthropic. I’m very interested to understand why.

ETH is relevant in many areas, but in this post I will describe its relation to recreational puzzle solving. In another post, I’ll very roughly outline the proof. I’m not going to talk about the LLM aspect at all.

[Read more…]

Link Roundup: November 2026

My link roundup skipped last month.  In the last two months, the ace journal club talked about asexual literary theory, and sexual pain in Christian women.  I also wrote a review of Portalmania, a short story collection.

Has the Navier Stokes equation been solved? | Stand-up Maths (video, 23min) – AI has been used to solve the Navier-Stokes Millennium Problem.  The Navier-Stokes equation is basically the equation of motion for classical incompressible fluids.  But after learning some of the details, I’m a bit disappointed.  Solving the Millennium Problem is not the same as solving the equation.  Instead, they proved that there isn’t always a solution.  Some initial conditions will result in a singularity. Of course in the real world, no singularity would occur, because the fluid would stop being classical and incompressible before reaching that point.

So the Navier-Stokes Millenium Problem is, deceptively, kind of a pure math problem without any immediate application.  If you want to actually predict the behavior of a fluid, there are already numerical methods available, and the Millenium Problem won’t help you.  Some mathematicians are pointing out that for pure math problems, the journey is more important than the destination, because that’s where we may learn new techniques.  That seems fair enough to me.

Why I am not an Effective Altruist | Tell me why the world is weird – Perfect Number discusses her disagreements with the EA approach to global poverty (to say nothing of animal welfare or ex-risk).  In short, she wants to give to causes that she has a personal connection with, even if they’re not necessarily the most optimal charities from the “objective” perspective.  e.g. a woman who benefits from women’s rights might want to donate to causes that fight for women’s rights.  Seems sensible to me.  Although I would say, global poverty is not exactly disconnected from us, we beneficiaries of centuries of colonialism.

I donate ~10% of my income, mostly to GiveWell, plus maxing out my political campaign contributions.  For all my misgivings about EA, Givewell seems pretty respectable and 10% a reasonable standard.  But I don’t feel much connection to any particular cause, and I generally find the prospect of choosing between charities to be stressful.

Spooktober 2026 | Life’s a Gas – Bébé Mélange has this series where they share an idea for a spooky novel every day.  I think these are neat.

Wealth Inequality in America | politizane (video, 11 min) – An video-infographic, with commentary.  If you follow the links, there are more about income inequality.

Voting is dissatisfying

Voting is dissatisfying. We spend however many days of the year being mad at the other side, and what does it come to? One vote. It’s not proportionate.

My thesis can be summarized in this graph.

plot of the dissatisfaction of voting

Plot showing political views vs political sway. The political sway that we want increases as our political views get stronger. But the power of the vote is a binary choice. So there’s a gap between what we want and the power of a vote.

The dissatisfaction is strongest for people who are most passionate, or who are on the far side of the spectrum. So it is you have leftists complaining that though Democrats “won” the 2026 election, now we have to deal with all the shit Democrats. There is a gap between what they desire (true leftist candidates) and what they can achieve (Democrats).

[Read more…]

Punishment of sexual violence

My politics tend towards anti-punitive. That is, I tend to favor smaller and shorter punishments for criminals. No particular reasons for it, no commitment to any philosophy or political movement. It’s moral intuition. When I imagine the appropriate punishment for a criminal, and I compare to what’s actually done, I find actual punishments sound too harsh to me.

This has long put me at odds with certain kinds of advocacy against sexual violence. I am in favor of holding perpetrators accountable, acknowledging and caring for victims, and pushing back against the culture that teaches men to become perpetrators. I am not and have never been in favor of harsher punishments for perpetrators.

Let me clarify. Many perpetrators face virtually no punishment. Victims are subject to ostracization and retaliation, and thus deterred from making any accusations. When accusations are made, the friends and community of the perpetrator close ranks and defend them. Police do virtually nothing. For the perpetrators who face no punishment, or are even socially rewarded, yes I favor a punishment that is harsher than zero. But for those perpetrators who are successfully held accountable, I do not advocate harsher and harsher punishments.

[Read more…]

Origami: Western Pond Turtle

Western Pond Turtle

Western Pond Turtle, designed by Robert Lang

This is one of the designs in Origami Design Secrets, in a chapter on pattern grafting.  The hexagonal pattern on the turtle’s pack is folded first, then you fold the rest of the turtle around it.  You can also fold the turtle without the hexagonal pattern.

It’s a different style from the other turtle I’ve shared.