Leprechauns are tricky even when they’re not

Neil L. is a Leprechaun.

Today I wish to share my experience with him this morning of St. Patrick’s Day.

Neil L. has visited me the last four years, so I was obviously expecting him to visit again this year. I stayed up late Saturday night, and as the clock hit 12:01am I expected him to appear any second. But no Neil. There I sat on my study sofa waiting. Soon it was nearing one o’clock and the combination of the soft sofa and the late hour overcame my resolve—I was soon fast asleep.

I was awakened to the sweet smell of smoke. The room was dark, and as my eyes adjusted I finally saw him standing next to me puffing on his pipe, each puff filling the air with green smoke. I nodded hi and asked him, why was he late this time? Neil said,

I forgot about Daylight Savings Time, it is earlier this year.

I said it was great to see him anyway, but did not add that the rules on Daylight Savings had changed in the US six years ago—perhaps he was kidding me—in any event I was thrilled to see him again.

I asked Neil, do I get some wishes this year? He laughed and took his pipe out of his mouth. He said,

I only give wishes if you catch me. Not the case this year.

With that he laughed and sat down on the sofa near me, and began to puff away on his pipe again.

I asked, why did he visit me anyway? He smiled and said he was still enjoying the way he had fooled me two years ago when I had three wishes and got nowhere. But last year when I had no wishes, he had let down his guard and almost given some secrets away.

That was a learning experience.

He said he felt I had some more to offer in learning to deal with human beings, and would like to test my perception. I wondered what he had in mind.

## A Challenge

Neil puffed some more on his pipe, and then with a twinkle in his eyes said,

I will grant you two wishes if you can guess my secret today. Good luck to you.

I looked at him and thought: what could his secret be? He was dressed as always, in green, with that hat; he had the same pipe, with the same smelling tobacco, with the same green smoke. I saw nothing special. What I could be his secret? He loved word games, but nothing he had said seemed to strike me as different. Here I was with that Leprechaun again, and yet I was at a loss for what his secret might be.

I asked him, would I get more that one guess at his secret? He answered after a short pause,

You get three.

Yes indeed.

I thought for a while and asked, “Is the secret in what you have said to me?” He replied,

Indeed indeed.

Hmmmm, I pondered: there was something strange about that last answer, why the repeat? I knew he likes to play with words. I began to see something. I quickly asked, “will you just say ‘yes’?” He looked perturbed and said,

I cannot just say yes.

I had a idea. It had to be it. I smiled and said, “I see your game: you are always in your prime.” He looked shocked. I knew his secret. Do you?

## Question I

I had “caught” him again, but since I hadn’t literally caught him in my arms or trapped him some other way, I only had two wishes. And Neil said they had to be questions, not wishes for things like gold.

So I had just two questions this year. I wanted them to really count. When I last had them, you may recall, I asked for proofs of certain problems and got nothing of value. He had beaten me. This year I resolved to be more clever. I thought that I might just ask, “Is P=NP true?” But even this worried me. Could he wiggle out by some trick? What if he said no, but simply meant that the symbols ‘P’ and ‘NP’ are obviously not the same. The logician Willard Quine was an expert at quotes and meanings of sentences, and I had studied him as a graduate student, years ago. But I worried that Neil would get around any question, perhaps using some quote trick.

So I asked Neil, “Can I ask you a question—a precise question—so that you will answer it the way I mean when I ask it, and not resort to some trick of language?”

Neil puffed on his pipe and replied,

Just so I understand about what you say and what you mean, may I have an example?

I wanted to make sure he understood concepts like polynomial time, so I phrased it this way: “If I ask you does a problem have an algorithm that runs in ${X(n)}$ time, can you understand that ${n}$ is the input length, and ${X(n)}$ isn’t in some literal units of time like seconds but asymptotic, and that constants or even lower-order terms like logarithmic factors don’t matter? The algorithm’s running time is defined up to all that.”

Neil drew forward and replied:

‘Yes’ to both your questions—I learned about time long ago from the Venerable Bede, who did the most to standardise our numbering of years. But note you’ve already asked me two questions. Luckily for you my answer still allows you to ask me a question—a precise question—so that I will answer it the way you said you mean, not by a trick of language.

I glowered—I had just let myself get tricked again. And I felt tricked by language: I hadn’t meant to use either of my two questions yet. Neil sensed my upset, so he volunteered:

I will make my answer valid for both worst and average case complexity, just as if you have asked them as separate questions.

Fair was fair, and I still in a sense had two questions. Better yet, I could ask a precise question and get it answered on my terms.

## Question II

Only one question left. If I asked about P versus NP, I would even get an answer about DistNP as a bonus. But I worried that would be too much to ask for, maybe not precise enough—moreover, I had spoken about running times and Neil’s promise was tied to that.

And most-case complexity matters for a question that has been in my inbox a lot these past two weeks, since we passed on the news from Dan Boneh at the RSA Conference about the breakthrough on discrete log. Recall he said there is an attack on discrete log that runs in time ${L(1/4)}$ where for all ${a > 0}$,

$\displaystyle L(a) = \exp(bn^a (\log n)^{1 - a}).$

Here ${n}$ is the number of digits in the input number ${q}$, and ${b}$ can be any constant—I didn’t have to say what ${b}$ is because it didn’t matter. In fact the whole ${(\log n)^{1-a}}$ didn’t matter—Neil would have to ignore lower-order factors—so only the ${a}$ in ${\exp(bn^a)}$ really mattered. The exponential security condition on discrete log and factoring is that there is some ${a > 0}$ such that ${\exp(n^a)}$ is a lower bound, indeed a most-case lower bound. This is what the slippage from ${L(1/3)}$ to ${L(1/4)}$ seems to threaten, what Adi Shamir used to say he believed in and people cared about, what even the “Natural Proofs” barrier about proving ${\mathsf{P \neq NP}}$ is technically based on. Breaking factoring would “destroy the world economy,” I had heard Alexander Razborov say in Washington, so I felt this was the most important precise question I could ask Neil:

Does there exist a positive real number ${a}$ such that factoring does not have an algorithm with running time ${L(a)}$, answering also for average case?

Neil responded quickly and forthrightly:

Yes—see?

—and vanished in a billow of green smoke.

I was amazed: no wordplay trick, I had a direct answer. And I was sure a lot of people in Washington and Virginia in particular would be thrilled to know of it.

With puffed-up satisfaction at having beaten Neil at last, I watched the smoke he left behind. I thought it would simply dissipate, but it didn’t. The smoke wound itself together like a thick short rope, then curled over so that it formed a letter—the letter

c

in a distinctly Gothic font. Then came the horrible realization: Neil had held to the letter and spirit of everything I’d requested, and had given me a mathematically correct answer, yet I had learned nothing.

## Open Problems

How had I been tricked? What is the relevance of c? Does watching this help?

Happy St. Patrick’s Day.

PS: His secret I caught was that the number of words in all his answers was …

March 17, 2013 12:37 am

The leprechaun can only speak in sentences that have a prime number of words.

• March 17, 2013 12:53 am

Some of Neil L’s smoke is still in the laptop—we are working on the problem.

• March 17, 2013 10:45 pm

Bill Gates was the real sprite here: I copied Mr. Anzel’s original English words into a Notepad++ window before playfully doing Google Translate into Irish/Gaelic, but without saving—and they were lost when Microsoft rebooted my office PC for updates.

For a hint on the other, I sometimes give this as a HW problem in our graduate theory course: Prove that there exist real numbers r >= 1 such that no Turing machine has a running time that is Theta(n^r). Characterizing such numbers is extra credit, could be quite a lot of it…

2. March 17, 2013 1:43 pm

next year ask “. . . with running time <= L(a)."

March 17, 2013 6:37 pm

I’m not sure to quite get the issue here — namely, when the question asks about the existence “an algorithm with running time L(a)”, is it Theta(L(a)) or O(L(a))? If the latter, then the monotonicity of L would prevent the trick (any way of “discretizing” the possible values of a into a sequence a_1,..,a_n,… with (a_{2k}) increasing to infinity and (a_{2k+1}) decreasing to 0 would cover all reals, and ruin Neil’s trick?

• March 18, 2013 9:10 pm

Yes, Ed above has it right too—and we worded the final question as “how had I been tricked?” rather than “how had Neil tricked me?” It is, however, an easy trap of definitions to fall into, “the running time” versus “runs in time…” (and I am often careful to write “runs within time…” for that reason). We thought the fact interesting for its own sake anyway…the idea of characterizing the real numbers a (or r in my comment above) that give running times leads to some nontrivial issues about limits, I think.

March 20, 2013 8:40 am

An undergraduate-level exposition of the 2013 Leprechaun’s Trick would be very welcome (to me and perhaps many readers) … uhhh … in my case a high-school-level exposition would be even better!

Assertions like “the number $r$ exists” seem to acquire extra-tricky gravitas when such assertions are embedded (implicity?) in tough-to-prove statements like “no algorithm exists whose runtime exponent is $r$.”

Might we hope for further GLL essays upon this topic?

• March 20, 2013 3:12 pm

For any two real numbers r,s with r < s, n^r = o(n^s), so no Turing machine can have running time Theta-of both. There are uncountably many real numbers, and only countably many Turing machines, so lots of real numbers are left over. The reasoning about “L(a)” is similar. But we don’t learn anything of significance about runtimes for rational values of r, for instance.

The Gothic c is a common symbol for the cardinality of the continuum, which may-or-may-not be the highest cardinality after aleph-null.

March 20, 2013 9:36 am

> […] tough-to-prove statements like “no algorithm exists whose runtime exponent is r.”
I too would be interested to learn more about the proofs of such statements, if they happen to exist. But it could as well turn out that the seemingly “easy” problems in NP are simply those whose polynomial algorithm is practical and has low enough Kolmogorov complexity to let us poor humans discover it…

March 21, 2013 11:29 am

Thank you Pip! It is natural to wonder what the Leprechaun King’s yes-or-no no-quibble answers might be to:

Q1  Is the set of languages in P totally ordered by lower-bound runtime exponent?

and

Q1  Which (if either) oracular answers to Q1 would have substantive implications for understanding complexity theory?

The world wonders (well, me anyway)! 🙂

March 21, 2013 12:48 pm

Those real exponents that are the running times of some Turing machine don’t seem to depend on the computing model, do they? So they really should deserve a special name… Is anything else known about them apart from their countability?

March 21, 2013 3:11 pm

LOL Serge, please let me suggest that you liven-up the forum TCS StackExchange by asking that question! E.g., if the question is phrased as:

Question  What reals are known to be lower-bound runtime exponents of TMs that decide the languages in P?

then it is not obvious (to me anyway) even that the integer 2 — or any other rational number? — is known to belong to the mysterious set of (as they plausibly deserve to be called) “Serge Numbers.”🙂

Considerable delicacy-of-definitions may well be required (per KWRegan’s post above). Good luck, Serge!

March 21, 2013 3:45 pm

Thank you very much John. Maybe out of modesty, I just thought they ought to be called Turing numbers…🙂

March 21, 2013 4:32 pm

Actually I was more interested in the algebraic/topological structure of this “Turing subset” of R (e.g. dense subfield?) and its possible relationship with the algebraic numbers… and also in what it might tell about the underlying computing model – provided that it does depend on it. But as you’ve suggested John, there’s certainly a lot of undecidability behind all this.

March 21, 2013 5:56 pm

It’s remarkable how little we know about the Serge-Turing (ST) numbers …

Q  Is ST membership decidable?
Q  Are the ST reals well-ordered?
Q  Is 2 an ST number?

We’re not sure (at least I’m not) how to pose these questions naturally and rigorously … even to helpfully oracular “Leprechaun King.”

No wonder P is hard to separate from NP!

March 24, 2013 9:41 am

The set of Big-Theta running-time exponents of polynomial Turing machines seems to be equal to the set of non-negative rationals… but I don’t know if it’s provable.

March 24, 2013 11:44 am

Yes. Runtime constraints that (as far as anyone knows) are undecidable in ZFC, are binding upon Complexity Zoo classification (because Complexity Zoo classification is decided by oracles, not ZFC theorems)  … in this sense the complexity theory community has for decades been striving (as far as anyone knows) to vastly extend ZFC. So ambitious a mathematical quest might daunt even a Leprechaun!

March 24, 2013 2:35 pm

Thank you John for this enlightening perspective. I wanted to conjecture that this subset was equal to the (non-negative) rationals if P!=NP, and to the algebraic numbers if P=NP. But it’s too much to claim as long as ZFC hasn’t been extended along the lines you’re suggesting. And it’s quite frustrating, because otherwise we could have felt like Pythagoras discovering the non-rational numbers…🙂

4. March 17, 2013 11:06 pm

Reblogged this on petemcneely.

5. March 18, 2013 10:50 am

did anyone else get the razborov ppt to display? it downloads as a zip file with lots of xml files for me & couldnt get it to work. from the following link
http://www.gwu.edu/~asl2010/img/razborov.pptx