Happy St. Patrick’s Day—Again Again.
Leprechauns and proofs
Neil L. is a Leprechaun.
Today I want to relay my experience with him this morning of St. Patrick’s day.
Neil L. came to see me today, he visited me the last two years, and fell asleep on my sofa waiting for me. It is a very comfortable sofa, one that I have used for “power” naps many times. Seeing him asleep I grabbed him. As he awoke he said: “The day, the day what a wonderful day. Please release me and let me go my way.” I said why should I? He remarked that if I let him go he would grant me three wishes. Any. I released him, and he pulled out a pipe and began to smoke. Green smoke came out, which had a surprisingly pleasant smell.
He then added they could not be “any” wishes. Leprechauns have magical powers, but he explained there are limits to my wishes. He said that over the years there have been some abuses of wishes and now there were rules among Leprechauns. The wishes had to be requests that required only information—I could not ask for money, or some strange power, or try to ask for more wishes. The rules went on for quite a while, and I started to become impatient. I wanted to make my first one. At last he nodded with a smile, “please ask away, on such a great day.”
Question and Answer I
The question I thought I had to ask is of course: Give me a proof that
What else? Well I might have asked for a proof that 
Neil L. smiled at my request. And after he blew a large green cloud of smoke from his pipe, there appeared in his small hand a single sheet of green paper. He said with a twinkle in his eye: “Here be a proof that 
The sheet had this written on it:
This is a proof that
. So suppose it is false, that is
But this implies that
. For large
this is clearly wrong and we have reached a contradiction.
I screamed this was nonsense—that is not a proof that 
I calmed down a bit and saw his point. He did give me a “proof,” of course a proof that was silly. Proofs can be incorrect and proofs can be correct. Okay I think I will have to restate my next wish more carefully. At least I had two more.
Question and Answer II
“I see your game Neil L., and I will be more careful with my next question.” He just smiled and took another puff on his pipe. This time I asked him: I want a proof that a professional mathematician would accept as a correct proof that shows the separation of the complexity classes
He said, “Clever. You could have gotten a proof by a great troll who knows her maths well, and only knows a long dead language.” Again after a puff of green smoke he handed me a book—it must have been over a 500 pages. He said with a twinkle in his eye: “Here be a proof that
I opened the book to the first page. Then scanned another page, and then jumped to the middle. It was mathematics. He had not cheated me there. But the proof was unreadable to me. Here are the opening sentences:
This is a proof that
-adic structure of the polynomials of locally bounded degree, is either final in the sense of Williams [71] or is near-final and is quasi-closed in the natural topology induced by the Fortnow-Tao ring [789].
The proof went on for hundred of pages like this. I quickly turned to the references. They were there, but some were to papers that were published in years ahead—one in the year 2033, for example. What is the “Fortnow-Tao ring”?—it had not been invented yet.
He had gotten me again. It was a professional proof, and might even be right, but I would never understand it.
Question and Answer III
I was now sorry I had let him go. He sat there looking at me with his pipe and puffing out green smoke from time to time. He seemed very happy with himself. He said, “You have one request left, what be your pleasure?”
I finally figured it out. I asked him
He waved good-bye and in a final puff of green smoke was gone.
Open Problems
Happy St. Patrick’s Day. What did I ask him? What would you have asked?
There is one more puzzle today—Neil L. has a secret, can you see what it is?
Trackbacks
- Valiant’s Permanent Contributions « Gödel’s Lost Letter and P=NP
- Leprechauns Are Tricky « Gödel’s Lost Letter and P=NP
- Happy St. Patrick’s Day—Again and Again and Again and Again | Gödel's Lost Letter and P=NP
- Happy St. Patrick’s Day 2014 | Gödel's Lost Letter and P=NP
- Leprechauns Go Universal | Gödel's Lost Letter and P=NP
Did you ask for a proof that would fit in a margin of the 500-page book? 🙂
Janoma
That would have been a better question.
“Clever. You could have gotten a proof by a great troll who knows her maths well, and only knows a long dead language.”
This kind of idea showed up in Douglas Adams’ “Dirk Gently’s Holistic Detective Agency”. At one point, at the end of his wits, the eccentric detective scribbles a bunch of total nonsense on a paper, then eagerly shows it to his client. “Look,” he paraphrases, “I’ve reduced the hard problem of solving the mystery to the relatively easy problem of translating the solution from some unknown language!”
Is his secret that his references do not appear in alphabetical order?
Joey
That is very sharp observation, but it is not the secret. It is just an error on my part. Although I guess there could be other authors I did not list to make all work out.
Hmmm … each puff of smoke is accompanied by the answer to a question. What was Dick left with, after Neil L.’s third puff of smoke, that he didn’t have before? Obviously … this column.
And so Dick’s question perhaps was “What column shall I post for this St. Patrick’s day?” And Neil L.’s secret is, that he is the author of it.
Either that, or Dick’s question was straight out of McSweeney’s Internet Tendency: “Wherever do you get that green-smoking pipe-weed?” 🙂
That is an outstanding question, and this is what I would say.
—–
(1) Leprechaun! Here is your first systems engineering question.
We systems engineers are so conservative that we implement only deterministic PTIME Turing machines (“tm’s”) that have decidable runtime exponents; we call this set of tm’s M’.
Moreover, with regard to decision problems, we engineers care solely about the languages P’ that are recognized by tm’s in M’, together with the larger(?) set of languages NP’ that are recognized nondeterministically by tm’s in M’.
So our first wish, Leprechaun, is for a rigorous yet engineer-unstandable answer to this question:
Of course, we engineers already “know” that the answer is “no”. What we want is a proof, so that the attention of complexity theorists is freed-up focus their attention on our second question.
—–
(2) Leprechaun! Here is your second systems engineering question.
For systems engineers, dynamical simulations are an important practical application of the tm’s in M’. Nowadays quantum dynamical simulations are particularly important.
One the one hand, we know that simulating noise-free quantum dynamics and/or error-corrected quantum dynamics is not in M’. On the other hand, we know also of many examples in which, for sufficiently strong Lindbladian dynamics, quantum simulation is in M’ (in consequence of induced compressive flow). Our second question seeks to close the simulability gap:
Of course, we systems engineers have a practical application in mind, namely the old dream of von Neumann, Wiener and Feynman … atomic-resolution quantum spin biomicroscopy and materials science. These devices have become sufficiently sophisticated—rather like commercial jet aircraft—that we quantum systems engineers have to simulate them in-depth, in order to design them and operate them.
—–
(3) Leprechaun! Here is your third systems engineering question.
Your answer to the second question has enabled us to design build quantum spin microscopes that are comparable to laserprinters in size, cost (and energy consumption). Thank you very much!
Now thousands of these microscopes are busy day and night, directly imaging (for example) the dynamic chromatin architecture that is associated to cellular healing processes. In consequence, we now are learning comparably much about genome dynamics, as we already know about genome sequences. “We must see, we will see” is our 21st century motto in biology, medicine, and materials science.
But it is not obviously true that “to see all is to know all” (uhhh … Stendahl?) and our third question seeks to close the see-all/know-all gap:
In summary, the preceding narrative summarizes the practical reasons why we systems engineers—together with very many patients who stand in need of healing—would be deeply grateful to any Leprechaun that could answer these three questions.
—
Now speaking personally, the Leprechaun’s answers would suffice for my answer to Gil Kalai’s MathOverflow question: A Book You Would Like To Write … and in recent weeks I have become reasonably hopeful that these answers will come sooner rather than later. In tribute to the wonderfully funny/serious Cohen Bros film A Serious Man: “May Hashem speed that day!” 🙂
So as not to quench the St. Paddy’s fun, here is a guess at Neil L’s secret (from searching MathSciNet for the keyword “leprechaun”):
The reference is to Scott Berry’s article Discrete search for an intelligent object: the Leprechaun’s Problem (1996).
The ability of leprechauns to hop from place-to-place is what makes them (perhaps?) NP-hard to catch, thus anyone who can catch a leprechaun has no *need* for informatic wishes! 🙂
You should have asked him for proof of Collatz problem – that should be easier to state 🙂
“What does a resolution to the P vs. NP problem look like, in a format that would win the Millennium Prize within the next year?”
After the first question, when you realize you need to be tricky, you could try “What is the question I should ask you to learn what I want to know about P v. NP?” You could then ask that question in the next round. (The idea from this came from “The Paradox of the Question” , which in turn I had seen on Dick’s previous post here )
Probably you could form a compound question of the above to take only one question. In fact, I guess you could ask arbitrarily many questions, by using “What is the answer to question 1 concatenated with the answer to question 2 concatenated with … ?” Be careful to make sure you will be able to parse the answers from one another!
I lost the links! The Paradox of the Question is here, and the old post was here.
1. “If P=NP, then (N-1)P = 0”
It is an interesting thought. But there is a mistake. N of P is no longer P but P’. Hence, (N-1)P is an invalid expression.
2. Continuation is the mathematical object and structure to separate the complexity of the two classes of P and NP. Continuation exist in in real domain and the imaginary domain. Continuation is NP by default.
John:
1. “We systems engineers are so conservative that we implement only deterministic PTIME Turing machines (“tm’s”) that have decidable runtime exponents; we call this set of tm’s M’. Moreover, with regard to decision problems, we engineers care solely about the languages P’ that are recognized by tm’s in M’, together with the larger(?) set of languages NP’ that are recognized nondeterministically by tm’s in M’.”
It is an incorrect statement. As I have proved, space and time are possible real quantities to construct non-polynomials. Space and time management does not terminate continuation. Space and time complexity helps to understand polynomials and non-polynomials. You misunderstand the cause and effect of the relation.
2. “Of course, we engineers already “know” that the answer is “no”. What we want is a proof, so that the attention of complexity theorists is freed-up focus their attention on our second question.”
It is an incorrect statement. It is a very important question for the Universe with space and time, physical mass gap, and computing theory and practices.
3. “Dynamical simulations are an important practical application of the tm’s in M’. Nowadays quantum dynamical simulations are particularly important.”
I have proved that scaling (scale in) can construct polynomials in lower orders. However, scaling back constructs non-polynomials. Hence, simulation is an application but not the direction. Hence, the first question is critical.
4. “simulating noise-free quantum dynamics and/or error-corrected quantum dynamics is not in M’.
As I have proved that phase incompleteness results in non-polynomials.
5. “What necessary and sufficient conditions ensure that a Lindbladian quantum dynamical system can be simulated in M’?”
See 3 and 4
6. “Of course, we systems engineers have a practical application in mind, namely the old dream of von Neumann, Wiener and Feynman … atomic-resolution quantum spin biomicroscopy and materials science. These devices have become sufficiently sophisticated—rather like commercial jet aircraft—that we quantum systems engineers have to simulate them in-depth, in order to design them and operate them.”
See 4.
7. “Your answer to the second question has enabled us to design build quantum spin microscopes that are comparable to laserprinters in size, cost (and energy consumption). Thank you very much!
Now thousands of these microscopes are busy day and night, directly imaging (for example) the dynamic chromatin architecture that is associated to cellular healing processes. In consequence, we now are learning comparably much about genome dynamics, as we already know about genome sequences. “We must see, we will see” is our 21st century motto in biology, medicine, and materials science.”
It is an operational example of ubiquity of polynomials and non-polynomials.
8. “By what practical clinical means can regenerative hippocampal healing processes be initiated, accompanied by an integrated and medically reliable dynamical understanding of the nano- and ultra-structural processes that are associated to this healing?”
Answer is scaling. See 4.
I would have asked for a self-contained proof. I am assuming you could have put an upper bound on the number of pages too?
It’s simple. You asked him to “Give me what I want you to give to me, now.” Then the onus is upon him to know what that is, not on you to specify what it is. 😉
TWO can play at the leprechaun’s game! 🙂
The question should be:
“Here are the definitions of the classes P,NP in the Coq system. Please give me a (correct) Coq proof that P!=NP, if it exists”.
The Leprechaun’s Restriction: “The wishes have to be requests that require only information.”
Ah … so this is a *STEM* leprechaun! That is, a leprechaun whose powers are restricted to Science, Technology, Engineering, Mathematics (STEM).
Well, math questions often are the most fun questions to ask of STEM leprechauns … because good answers bring a kind of immortality for the asker and the answerer.
But just at the moment, perhaps practical information is a higher priority. Maybe we should ask the STEM leprechaun this:
Hmmmm … since we still have two questions left, we might ask these:
These seem to me to be among the three most urgent questions, that we can ask of the STEM leprechauns that (really) live inside of all of us.
Being outwitted 2 times in a row, I would lower my bar and ask a program for Turing machine that solves sat problem in P time if such program could exist, and some of that stuff that goes into his pipe if not. We would still lack the proof that it runs in P time but we would get usable algorithm!
Ah wait, knowing mr. Neil L., it would run in P, but it would still probably unusable in real world because of very high order of P. Forget it!
How about asking:
“Is it possible to encode a complete and valid proof that P=NP in a finite number of bits?”
He may get tricky on the definition of a “bit” however.
John:
“Conjecture: Optimal search strategies in the Leprechaun’s Problem are NP-hard to compute.”
Conjecture should be based upon possible true statement. Do we still have “HARD” problem ?
The reference is to Scott Berry’s article Discrete search for an intelligent object: the Leprechaun’s Problem (1996).
Why it has to be discrete search ? Does the incompleteness of the “Intelligent object” have zeros ? Did you apply kernel scaling, relation scaling, and q-scaling, etc ?
Please don’t take that post *too* seriously … since childhood I have been very fond of the word “leprechaun” (I have an Irish grandfather), and so it was great fun to search the AMS reviews for that word … and find it.
As for the striking bimodal distribution of “leprechaun” prevalence in Google ngrams … heck, that’s completely mysterious. For some imponderable reason, during the years 1941-1947, pretty much *everyone* was writing about leprechauns.
Maybe we should ask the leprechaun how that came about? 🙂
Seems strange that he would let you catch him so easily.
I have few words from troll.
They were related to max-cut problem reduced to binary quadratic program, which in turn is reduced to minimizing specific Quartic polynomial
, where 
matrix representing edges, which in turn can be relaxed to sum of polynomial squares program, which is solved in polynomial time by the Semidefinite program. Troll said that the relaxation is tight enough for small 
, at least linear in it, that allow arbitrary precision approximation of the max-cut problem, which in turn, allow to find the cut.
The dead language I was provided, reminded me real algebraic geometry. Unfortunately, I have no knowledge in this area, and was not able to decode the message in a readable format. It seem that the problem is within known techniques, but out of few the people I know who would be able to check this fast, were too much biased by their believes, that they did not try to decode it, I think they even did not look at the text.
I think you should try to prove three clear, simple lemmas: that the polynomial is indeed a relaxation of max-cut, that it can indeed be arbitrarily tight, and that it can indeed be solved in polynomial time. My humble conjecture is that at least two of these lemmas will turn out to be false, and you will see your mistake very quickly after you put in a bit of effort.
Optimization of polynomial is reduction/relaxation of max-cut depending how do you count limit operation. See me in archive, or in P. vs NP page. SOS program can be solved in polynomial time, this is Parrilo and Shor, so at least two of your lemmas are true. The question is how tight it is. This is beyond my abilities, and as far as I know it is open question in real algebraic geometry. What is known is that not all non-negative polynomials are representable as sum of squares. There is no good classification with respect to this topic. Practically, all reasonable non-negative polynomials are sums of squares modulo their gradient ideal. This is J. Nie, although there is very weak bound on degree.
It always worked in practice, and there is no reason to have some special cases, except for
, which is super-symmetric. For any non-zero 
you can modify max-cut, adding small perturbations that there is unique perturbed maximal cut, that coincides with (one of) non-perturbed maximal cut(s).
You have words from troll, whether to check them, or to go away is your choice. And I already told that I do not want to change any believes. People will come there with their own pace. The progress in science is not because someone changes his/her believes, but because new generation growth.
Your transformations may be correct in the weak sense that they preserve the optimum, but not in the strong sense of preserving the approximation factor. It is perfectly possible to start from a hard-to-approximate problem and transform it to an “equivalent” problem that has a PTAS, but says nothing about the original problem. That I believe is the largest of the many gaps in your approach.
I pretty sure you do not, and do not wish to understand what I’m talking about. If we would reverse I would do the same. In general you are right, but for P=NP it is sufficient to show only one working algorithm, where all the (known) rest would not work – meaning pay attention for details. If you have real algebraic geometers as friends translate them P=NP problem, the people I know close to field, see this problem being not interesting, and ask them what they think about sos approach. Among the people publishing in related areas, only one responded me, generally stating (say, for short) Hilbert 17th problem, and that not all non-negative polynomials are represented as a sum of squares. I’m the wrong guy to talk to, but I cannot convince the right guys to look at it, or may be it is too difficult for modern math. It related to a particular question about particular narrow class of polynomials, may be too narrow for modern tools. Since nobody talks to me (what they should do), I have no idea what is real state of believes among professionals.
I understand the ignorance, since the problem associated with fame, and money.
I understand I’m not the smartest man on the Earth. I do not pretend for the money. I think they even slow down the process. Get it technically correct and publish, whatever result you get, in any case you get something interesting.
This problem is tightly bound with unsupervised learning. And can have many applications associated with safety (,where can reflect the willingness of humans to pursuit the issue), machine learning, etc. Another problem may lie in psychology, the fact that P=NP many should be intuitively afraid of – they can be replaced with computers. So it takes time to get used to that thought.
Some guesses at Neil’s secret:
(1) “Neil L. is a Leprechaun.”
For some reason, I read your opening sentence as “NL = L”. Setting aside that bold claim for the moment, I am pretty dubious that wish-answering green guys are in logspace, non-deterministic or not. Maybe it’s mythologically implicit that all Leprechauns are Nondeterministic, in which case you’re teasing us with a tautology.
So maybe Neil’s secret is that he’s just “pretending to be short” (ie. logspace), when he’s probably a Merlin-class mythological entity.
(2) In the picture of Neil, his shoulders are represented by lunes. However, Neil has extremely robust computational (or oracular) abilities, so he is obviously a square-shouldered gent. Perhaps he is reminding us of Hippocrates’ quadrature of the lune, and hinting that just because you can get something out of him (existence of the proof you desire / quadrature of the lune) doesn’t mean you’ll be able to extend it to what you really want (a usable proof / squaring of the circle).
(3) His shamrock has way too many leaves (even if one of them turns out to be a jpeg-mangled stem).
Christopher H,
The secret, I guess is too good, is Neil L. never uses the letter “i”. I thought I would work this in somehow, but it was hard to avoid I’s. Notice he says “be” alot instead of “is.”
Aha — the intended answer is not “natural” relative to the class of Leprechauns (in the sense that it depends upon idiosyncracies of English-language idiosyncrasies). No wonder it’s hard to answer!
It is not easy to conceive puzzles whose answers are surprising and delightful *and* mathematically natural. This distinction is particular evident in card tricks, the lesser of which rely wholly upon sleight-of-hand, and the greater of which rely largely or even wholly on surprising combinatorical and informatic mathematics.
The fact that the Faro shuffle works may be surprising and deep, but I would be far more surprised if I woke up one afternoon and found that I could actually do the thing, much less 7 times in a row without fail.
(This is a bit off-topic, but I’ve always thought the more surprising fact was that if you name any two different card values in a deck, you will find two adjacent cards in the deck with those values with high probability. It’s a very tricky probability to calculate. Anyone know where I could find out where someone has done it?)
I know this is old, but there’s a problem:
“but the sheet has a proof—perhaps not the one that you were looking for—but a proof.”
“Looking” has an “i”.
BIll
Thanks I missed that…oh well
I would have asked him where I can find/catch another leprechaun…
or
Did Fermat really prove his Last Theorem?
or
What problem will be at the center of theoretical computer science in 2100?
or
Will a new, physically realizable model of computation make the P vs NP question obsolete before 2100?
Modulo formulations of the questions, which result in getting useful information as an answer and not just “yes/no”.
(however, I’m not sure, if the last two question rely only on information…)
Our UW Quantum Systems Engineering team discussed both “leprechauns” and “gremlins” this afternoon, and we discovered both important clues and deep questions regarding their mysteries.
An important clue is the startling surge in the Google ngram frequency of leprechauns versus gremlins for the interval 1941-47.
Obviously, the years 1941-47 were very important for both leprechauns and gremlins … and yet (at present) we have no mathematically natural understanding of this correlation! 🙂
A second, potentially even deeper mystery is this: according to Google books, leprechauns and gremlins are almost never seen in the same book during these years. Why is *that*, one wonders! 🙂
Well, Neil L. did give you the proof, didn’t he? That can be considered as a proof that P != NP, just, well, outside of math. Thus third question can be completely unrelated, or there might not be any question at all.