May the best day of your past be the worst day of your future.

Neil L. is a Leprechaun. He has been visiting me or Ken once every year since we started GLL. We had never seen a leprechaun before we began the blog—there must be some connection.

Today we want to share the experience we had with him this morning of St. Patrick’s Day.

Here is my best reconstruction of what happened:

It was Tuesday, already St. Patrick’s Day in Ireland, and Ken and I were on a Zoom connection working late. We had agreed to skip any post highlighting Neil. We intended to highlight another female mathematician or computer scientist. And Neil is definitely not a female.

We never know in advance whether or when Neil is coming, but this time we took some steps. First, I am not where I was, and I made the finding task harder. Kathryn set up mirrors in my new study, since leprechauns fear being held by a stare. Ken is where he’s always been, but being still a few days from his first vaccination, knew Neil would respect the CDC guidelines.

We thought all was well and were discussing Hilbert’s Tenth until Ken spotted the puff of green smoke in a mirror behind me. Before he could warn me I heard the familiar voice to my side:

Top of the evening to ye.

I might have let him take off his mask and get comfortable, but instead I retorted, “Neil, thanks for visiting, but Ken and I have other plans. This whole month is dedicated to honor female researchers. So nice to see you as always, but …”

Neil smiled—we could tell that through his mask—and said:

Well, we could talk about a certain female Leprechaun—one who just solved a big problem in complexity. A problem that rhymes with “slower hounds in crime.”

Neil’s Dilemma

I was doubly confused: once by the cryptic rhyme, but then because I realized Neil—masked or not—was simply, provably lying. I hesitated to confront Neil because I recalled a book titled Leprechauns Never Lie, but Ken flashed the proof by sharing his screen over Zoom:

“Neil, there are no female leprechauns. We all discussed this two St. Patrick’s Days ago. Quoting my link: there is no record in Irish folklore of leprechauns having a female counterpart in their ranks or even a solid record of how they procreate or reproduce.”

Ken and I realized there was more than just the truth or female researchers at stake: a leprechaun caught in transgression must surrender his treasure. His treasure. But that was bound to make Neil extra tricky.

Neil was right on that wavelength, because his first words in reply were:

“Before we proceed, there is a matter about my pot of gold that we must resolve. And it will tie to the larger matter at hand. I need expert help, and ye be the two best I know to ask.”

What would Neil need to ask us? We had always tried to pin him down into telling us the answer to P=NP. Remember, a leprechaun cannot lie, so his answer would rule. So we said, “what do you need to ask?”

“I need to ask you about the meaning of P=NP.”

Neil’s Question

I bid Neil sit down and remove his mask to puff his pipe. I started to give the same answer I’ve given in countless classrooms: “P=NP means that a certain big class of problems could all be solved by an algorithm that runs in polynomial time. Polynomial time means…” But Ken cut in more pointedly:

“Neil, why do you need to know about P=NP? And to know what about it?”

Neil puffed on his pipe and gave what we could tell was an honest answer:

“We Leprechauns have started thinking about going modern—belonging to the 21st century. I plan on getting rid of my pot of gold coins and going into Bitcoins. Those pots are heavy to lug for us wee folk. But to judge if it be safe in our world, we need to know the gist and risks in your world.”

I switched gears and said the gist is that Bitcoin is based on a technology called blockchain that creates an unambiguous single history of recorded transactions, including how the coin was earned in the first place. The history does not need to be maintained by any trusted party—it is decentralized, and any party can access it to provide a proof of a record. Ah, but if P=NP…

Ken cut in: “If P effectively equals NP. Not the time for SAT or the huge constants from forbidden-minor sets kind of P=NP. If you can be really efficient at it then you can spoof a proof of an alternative history of records, one to your gain, or certainly put confidence in the other side’s version of events in doubt. Actually, something weaker than P=NP suffices.” We were next going to educate Neil on crypto, but he cut us off.

“We ken that cheana féin—well already. But what if your world have no unambiguous single histories to begin with? How déan that change the effective meaning of P=NP?”

Law and Lore

The essence of Neil’s question escaped us at first. We replied that the notion of “history” involved was like a computation by a deterministic Turing machine , and time is uniquely defined by its sequence of configurations Ah, Neil replied, cannot there be a that is reached by two separate paths, and ? If you are at and yet to go to you may have no inkling of at present—your present.

Ken cut in by saying that every computation can be performed by a reversible Turing machine —so that there is only one possible past history—and that is built from by propagating part of the computation’s history somewhat as blockchain does. But that did not help our argument with Neil. When Ken brought up the reversibility of quantum computation, Neil was ready with the Consistent Histories interpretation of quantum mechanics. The determinism of quantum evolution is at a “bird’s eye” level higher up, whereas in our “frog’s eye” experience the theory gives us probabilities over alternative histories and , and consistency rather than unique actuality is the criterion for their viability.

At this point I started to kick a stone at Neil about there being just one flesh-and-blood real world, with natural laws and a unique history, but his next words cut to the quick:

“On what basis then did ye dun me for speaking o’ female leprechauns? On the basis of lore, ye said. But is that as unchanging as the stone ye would kick at me?”

Ken got what Neil was saying and flashed a topical item on his Zoom screen:

“This came after our discussion two years ago—in which you referenced Notre Dame—but maybe you are right that its significance is before.”

I told Neil I still don’t agree about histories, but I withdrew our claim on his gold. Ken showed his face back on Zoom and was looking impatient so I gave him the floor.

“What Neil is on about is that many things we’d consider aspects of Leprechaun World are really theorized properties of our world. So we must ask, what if they are just one world?

Take Bitcoin. Now it’s obvious why Neil and friends want to get involved with Bitcoin. There are so many more ways to play tricks with it than with pots of physical gold. We wrote last year and many times before about the gaming and crypto tricks they can play.

But it’s nothing that we can’t do ourselves. So leprechauns make their pots of gold vanish? We’ve done that via Bitcoin quite to perfection—hundreds of millions of dollars poof!, no leprechauns involved.”

Neil’s Slower Hounds

Ken was about to say that this was the larger context of Neil’s question about P=NP but I recalled the second thing Neil said at the start and wanted something in return for letting go his gold. “Neil—I can grant female leprechauns but you said something else: that one proved a breakthrough in complexity. You said it rhymed with “slower hounds in crime”—ah, lower bounds on time. Neil puffed and said,

“Aye.”

“Can you tell us what she proved? We answered your question—and since you raised this to begin with, it’s only fair.” Ken chimed in by asking, “no one we know in our field is a leprechaun, right?”

“I cannae tell ye in the here of now, for a reason that ye conceded to me. Ye will appreciate something from when ye reach from . So I shall leave ye do what ye be doing.”

Neil turned as if about to wisp away, but a cry from me stopped him: “No final trick this time?” He gave us both a look that was sad and loving at the same time, something we didn’t know leprechauns could do. But he said,

“No trick that ye not be increasingly doing by yourselves.”

And with that he departed in a flash. The flash kicked onto my screen where Ken still was. In Ken’s place was an image I recognized as from the Bayeux Tapestry—that great record of history a millennium ago—until I looked a little closer.

Open Problems

Happy St. Patrick’s Day 2021, and may happier days be ahead.

[some word changes]