The NP genie
Hi from the Q2B conference!
Every nerd has surely considered the scenario where an all-knowing genie—or an enlightened guru, or a superintelligent AI, or God—appears and offers to answer any question of your choice. (Possibly subject to restrictions on the length or complexity of the question, to prevent glomming together every imaginable question.) What do you ask?
(Standard joke: “What question should I ask, oh wise master, and what is its answer?” “The question you should ask me is the one you just asked, and its answer is the one I am giving.”)
The other day, it occurred to me that theoretical computer science offers a systematic way to generate interesting variations on the genie scenario, which have been contemplated less—variations where the genie is no longer omniscient, but “merely” more scient than any entity that humankind has ever seen. One simple example, which I gather is often discussed in the AI-risk and rationality communities, is an oracle for the halting problem: what computer program can you write, such that knowing whether it halts would provide the most useful information to civilization? Can you solve global warming with such an oracle? Cure cancer?
But there are many other examples. Here’s one: suppose what pops out of your lamp is a genie for NP questions. Here I don’t mean NP in the technical sense (that would just be a pared-down version of the halting genie discussed above), but in the human sense. The genie can only answer questions by pointing you to ordinary evidence that, once you know where to find it, makes the answer to the question clear to every competent person who examines the evidence, with no further need to trust the genie. Or, of course, the genie could fail to provide such evidence, which itself provides the valuable information that there’s no such evidence out there.
More-or-less equivalently (because of binary search), the genie could do what my parents used to do when my brother and I searched the house for Hanukkah presents, and give us “hotter” or “colder” hints as we searched for the evidence ourselves.
To make things concrete, let’s assume that the NP genie will only provide answers of 1000 characters or fewer, in plain English text with no fancy encodings. Here are the candidates for NP questions that I came up with after about 20 seconds of contemplation:
- Which pieces of physics beyond the Standard Model and general relativity can be experimentally confirmed with the technology of 2018? What are the experiments we need to do?
- What’s the current location of the Ark of the Covenant, or its remains, if any still exist? (Similar: where can we dig to find physical records, if any exist, pertaining to the Exodus from Egypt, or to Jesus of Nazareth?)
- What’s a sketch of a resolution of P vs. NP, from which experts would stand a good chance of filling in the details? (Similar for other any famous unsolved math problem.)
- Where, if anywhere, can we point radio telescopes to get irrefutable evidence for the existence of extraterrestrial life?
- What happened to Malaysia Flight 370, and where are the remains by which it could be verified? (Similar for Amelia Earhart.)
- Where, if anywhere, can we find intact DNA of non-avian dinosaurs?
Which NP questions would you ask the genie? And what other complexity-theoretic genies would be interesting to consider? (I thought briefly about a ⊕P genie, but I’m guessing that the yearning to know whether the number of sand grains in the Sahara is even or odd is limited.)
Update: I just read Lenny Susskind’s Y Combinator interview, and found it delightful—pure Lenny, and covering tons of ground that should interest anyone who reads this blog.
Follow
Comment #1 December 11th, 2018 at 2:38 pm
I would think you could ask it for short proofs of whatever mathematical conjecture you want: Is there a proof, drawing on the existing mathematical literature and less than 500 pages long, of — the Riemann conjecture? P != NP? etc.
Comment #2 December 11th, 2018 at 2:43 pm
Another question: Is there a procedure, executable in a lab, that will mimic the emergence of life on the early planet Earth?
Comment #3 December 11th, 2018 at 2:44 pm
Hey, genie, imagine the set of all possible valid questions that you could answer.
Now answer them all, please 🙂
Comment #4 December 11th, 2018 at 2:57 pm
What is the best way for humans on Earth to communicate with an extraterrestrial civilization that would highly benefit our own civilization?
Comment #5 December 11th, 2018 at 3:11 pm
I think a good philosophical question that would be ground-breaking if correctly answered would be “Which regions of the brain are both necessary and sufficient to allow sapience to arise?”
Comment #6 December 11th, 2018 at 3:20 pm
I’m not sure that your “Ark of the Covenant” example works. A witness to an NP problem has to be easily verifiable. But, supposing that you did find physical remains that are in fact the Ark, how could you verify that?
Comment #7 December 11th, 2018 at 3:38 pm
1. “Which philosophical ideas about happiness, well-being, and value reflect the limiting result of thoughtful deliberative reflection on what we ought to value in the world?” [Checkable by seeing if philosophically thoughtful people are convinced by the answer, or can be persuaded away from it.] [If this yields inconclusive results, narrow the scope of people to those who more closely share your fundamental values (e.g. consequentialists).]
2. “What empirical paradigms and exact numerical measurements effectively capture this notion of well-being and value in the world?”
3.1. “What questions, if any, yield an answer from you whose outcomes, if implemented, measure at least 1 on this scale?”
3.2. “What questions, if any, yield an answer from you whose outcomes, if implemented, measure at least 2 on this scale?”
3.n. [Binary search on the above]
4. [The winning question from the 3.n’s]
But more seriously:
What ideas and questions in mathematics would yield especially valuable new research if explored further?
What sort of paradigms for AGI allow for verifiable alignment or corrigibility, in a way that we could have trust in the AI’s alignment with humanity’s goals despite its vast cognitive advantages over us (and for which the paradigm’s verifiability is itself verifiable, and so on)? [By assumption on the meta-verifiability, this answer would be one we could check.]
Which charitable interventions would demonstrate excellent good done in the world when investigated at scale by a large randomized controlled trial? As I understand it, a lot of the work done by e.g. GiveWell is just the search for high-impact charitable causes.
Which individuals would do immensely valuable and important work in the world, if they were given the resources to do so? [Imagine a world with 50 Ramanujans across different fields every generation!!]
What genetic markers indicate [trait] and could be verified by genome sequencing of the relevant people?
Which medications would effectively treat my condition?
Generalizing: Which chemical compounds would yield effective medications to treat this condition?
From a more self-serving point of view: What piece of text of length 1000 characters or less would convince X to do Y? What is the credit card number of this person? What are the passwords to the following email accounts? [Cryptography question which I assume someone has looked into: in a world where an NP genie is ubiquitous, how do you do security or encryption? Can you, at all?]
Comment #8 December 11th, 2018 at 3:51 pm
Dandan #3: Already dealt with in the post. Did you read it? 🙂
Comment #9 December 11th, 2018 at 4:23 pm
1. Blueprints for a practical fusion reactor.
2. In terms of Biblical artifacts, I would really like to get directions to manuscripts of the mysterious books mentioned or quoted in the Bible: The Book of the Upright (mentioned in Joshua and 2 Samuel) or the Book of the Wars of the Lord (quoted in Numbers).
3. Or, really, any of thousands of long lost manuscripts. One of Sophocles 60 lost plays. The MS of Oscar Wilde’s novel “La Sainte Courtisane Or The Woman Covered With Jewels”, which he lost in a taxi cab. The catalogue to the Library of Alexandria (the Pinakes).
Comment #10 December 11th, 2018 at 4:36 pm
I just want to highlight an issue here, which is basically that humans are stupid (though even just plain fallibility would suffice). E.g., I want to solve global warming. Your oracle lets me ask “what’s a plan for solving climate change that humanity will expect to work?” But, of course, the set of valid plans to solve climate change is not the same as the set of plans that sound like a good idea to humans. Even if we take something that’s easier to verify, like “where is a star that will appear to humans as though it has life around it” seems… risky.
Maybe some of these things could be dealt with via some kind of binary search. Like, if you could somehow quantify how good a plan seems, then you can use binary search to find a plan that nearly maximizes this quantity. You can even go further by kind of sort of climbing the polynomial hierarchy. E.g., given a fixed plan for solving climate change, we can at least ask “does there exist an argument that will convince us that this is a really bad idea?”
Even with these techniques, my suspicion is that an adversarial oracle is far more likely to lead to dystopia than utopia…
Comment #11 December 11th, 2018 at 4:41 pm
What was Fermat’s “slightly too large to fit in the margins” proof of FLT?
Comment #12 December 11th, 2018 at 4:47 pm
Raoul #11: I wouldn’t even waste a question on that one. Multiple lines of evidence—for example, the fact that Fermat was later excited about (correctly) proving FLT for the special case n=4—make it completely clear that he didn’t have a proof. He was just temporarily misled into thinking he did, as many of us are all the time, certainly in private scribblings.
Comment #13 December 11th, 2018 at 4:49 pm
Dandan #3: You, five seconds later, standing in the Library of Babel: “Oops.”
Comment #14 December 11th, 2018 at 4:53 pm
(I guess my vague notion of “plan for solving climate change” can be replaced by “design for a fusion powerplant” with various efficiency and safety constraints, but I think the problem that humans are poor verifiers still applies.)
Comment #15 December 11th, 2018 at 5:30 pm
Sorry, I had missed your “1000 characters or less” limitation. That knocks out several of mine, several of other people’s and is pretty tight on your “Give me a hint about P vs. NP”.
I don’t see that it’s at all compatible with your first question, “Which pieces of physics beyond the Standard Model and general relativity can be experimentally confirmed with the technology of 2018? What are the experiments we need to do?” unless by “pieces of physics” you mean existing theory that have a short name like “string theory” and the experiments have 300 word summaries.
Comment #16 December 11th, 2018 at 5:33 pm
Ernest #15: Of course, I just meant whatever hints the NP-genie could provide within the stringent character limit, provided there existed any hints at all that would suffice for eventual verification (not implausible to me).
Comment #17 December 11th, 2018 at 5:50 pm
What is the smallest counter-example to the Riemann Hypothesis (or the Collatz Conjecture, etc.)? If the genie answers, then the hypothesis is disproved. If the genie fails to answer, then any solution must be greater than about 10^1000.
Comment #18 December 11th, 2018 at 6:18 pm
Ernest #17: Counterexample to Riemann is a bona fide NP question, but a counterexample to Collatz might itself take an inordinately long time to verify. (Of course, one could simply ask the oracle whether an easy-to-verify counterexample exists. Personally, though, I’m sufficiently convinced that RH and Collatz are true not to waste my question on such things. 🙂 )
Comment #19 December 11th, 2018 at 7:05 pm
What are the next 83 sets of winning powerball tickets with a jackpot above $100 million?
Follow-up: what strategy for claiming and investing the winnings ensures I remain anonymous and secure?
Comment #20 December 11th, 2018 at 7:36 pm
Avi #19: Unless you can remain anonymous to everybody, including the lottery company, I don’t think you could possibly get away with winning more than a few of those jackpots. Either common sense or a Bayesian calculation would say, after your first several wins, that you were cheating with probability ~100%. (Unless you were buying crazy numbers of tickets, but that would be a high-effort alternative to just winning fewer jackpots.) I suppose your best chance would be to rely on 83 trusted intermediaries to buy the tickets and share the winnings. That would carry its own set of serious risks, though.
Comment #21 December 11th, 2018 at 7:36 pm
What is the order of the six questions that Scott asks in his post, so that Scott’s true preference is reflected?
If the NP genie provides no different order (of preference) that the one in the post, given that the Ark of the Covenant is placed before P vs. NP, I guess Scott really wants the Ark to be found!!
Comment #22 December 11th, 2018 at 7:58 pm
Avi #19 & my own first reply: Also, I’m not sure how the genie could give you those numbers in the first place, unless the game really was rigged. What convincing evidence could you be shown, before the fact, of the outcome of a random process?
Even if we assume it is technically deterministic, that doesn’t seem to help much unless the pseudo-randomness is very badly flawed. (Either the pattern or an algorithm for finding it would have to be shared with you in 1000 characters.)
Comment #23 December 11th, 2018 at 8:58 pm
Alex #21: I actually had P vs NP first in an earlier draft, but then moved it down because it seemed too obvious…
Comment #24 December 11th, 2018 at 8:59 pm
On the lighter side:
1) What’s the best Magic: the Gathering deck in [Constructed format of your choice]?
2) What’s a very funny joke you can tell in 1000 characters or fewer?
3) What’s a link to an online dating profile of someone that [I/my friend] would have a good romantic and sexual relationship with if [I/they] were to contact that person?
Alternate to 3: Who is [my/my friend’s] “true love”?
Comment #25 December 11th, 2018 at 9:04 pm
That’s almost the opposite of science, so I would just kill the genie.
Comment #26 December 11th, 2018 at 10:02 pm
I’m surprised you didn’t mention the big one- where can we find evidence that Donald Trump conspired with the Russians?
Comment #27 December 11th, 2018 at 10:19 pm
Scott #23: Haha, makes sense…
For anyone who is interested: until the NP genie pops out of anyone’s lamp (I guess Scott’s lamp has priority, since he was the one to conceptualize it) and starts answering our NP questions, let me say that I recently read a paper (arxiv.org/abs/1811.07401) and it may not be a sketch of a resolution of P vs. NP (as Scott’s 3rd question states), but it is a sketch that may say something new about P vs. NP. A professor of mine made me see that it contains ideas from which experts could get inspiration.
Comment #28 December 11th, 2018 at 11:00 pm
Michael #26: Again, not worth wasting a question on. Facts in the public record made it obvious since even before the election that they did collude, modulo uninteresting hairsplitting about the meaning of “collude.” Like, Trump openly urged the Russians to hack the emails. In the norms that used to apply, in the world that made minimal sense, that would already count as collusion and prevent him from being president (along with ~500 other violations of basic democratic norms). I’d rather ask the NP-genie: what can we do or say to get back to that world?
Comment #29 December 12th, 2018 at 6:54 am
Is the middle excluded?
Comment #30 December 12th, 2018 at 7:25 am
I’d ask for the best short description of how consciousness arises, to be elaborated by experts. This differs from Naiim #5 since I don’t believe the human brain structure is necessarily the best way to approach this.
Comment #31 December 12th, 2018 at 7:59 am
How much wood would a woodchuck chuck if a woodchuck could chuck wood?
Comment #32 December 12th, 2018 at 8:22 am
New rule: when proposing your question, you also need to explain how the genie’s answer would be verified if it isn’t obvious.
Comment #33 December 12th, 2018 at 9:41 am
Lou #30 That’d be a good start to answering the question, but as a cognitive neuroscientist, the only real answer that would finally help us to understand sapience is a more complete understanding of the organization of our cortical structures. If we don’t understand how the brain works together to allow us to process information sapientially (is that a word?) then we’re missing the fundamental part of what allows us to process information so differently than other organisms.
Scott #32 A good way to verify this is through lesion studies or TMS. Assuming that the genie answers with the truly sufficient and necessary cortical structural integrations, then shutting down or short-circuiting any of these circuits should cause us to lapse into a non-sapient state, verifying the genie’s answer. If we don’t, then we can tell the genie was wrong.
Comment #34 December 12th, 2018 at 1:05 pm
Just curious, Scott- why do you consider it so important to find Biblical artifacts? Do the details of how those stories arose have any relevance today?
Also, it is fairly uncontroversial that both the Ark and Jesus did exist in some form. So finding records of either of those wouldn’t necessarily teach us anything new. The Exodus, OTOH, is a much more open question.
Comment #35 December 12th, 2018 at 1:55 pm
Ahron #34: Yes, I think that elucidating exactly how the Biblical stories arose is one of the great research projects for the archeology and history of Western civilization, and that even (or especially) a hardcore atheist should have little problem agreeing to that claim. (Questions surrounding Homer and Shakespeare are not far behind.)
A Google search will return plenty of scholars arguing that neither the Ark nor Jesus might have ever existed, though I agree with you that they most likely did.
But it’s frustrating that our knowledge of events that came to loom so large over human history comes down to us through such a narrow channel, and through narrators who had specific axes to grind and no understanding of modern science and who were likely recording second- or third-hand information (in the case of the New Testament), or often much further-hand than that (in the case of the Old). Even if we reject all the miracle stories, that still leaves a huge range of defensible positions about how much of the rest of the narrative is likely to have occurred.
As one example of what could in principle be learned: can you imagine a worse nightmare for a rabbi (or for that matter, a priest or imam) than if archeologists finally found the Ark, and it turned out (as some have speculated it did) to contain statues of pagan gods like Ba’al and Asherah, rather than the Ten Commandments?
(There already indications from archeology, for example the findings at Kuntillet Arjud, that pagan gods may have played an even larger role in early Judaism than the Bible itself implies they did, in the course of railing against the tendency. On this theory, the idea of monotheism only arose later—probably around the time of the Babylonian exile—and was then retconned onto earlier events.)
Comment #36 December 12th, 2018 at 2:33 pm
Naiim #33, as a mechanistic neuroscientist, I suspect the way the human brain achieves consciousness will be just one case of a much more general solution. If we find conscious aliens, or conscious machines, I suspect their processing elements will not mimic that of the human brain.
Scott #32, asking for the short principle(s) behind consciousness is exactly the same as your request for a sketch of the solution of P ?= NP. Would even the best 1000 character explanation be enough to enable the details to be filled in? Unfortunately there is no way to know until you get the answer, so it’s a gamble. But, for example, the article “Introduction to Fermat’s last theorem”, page 13, has a roughly 1000 character overview of the proof, so it’s not a crazy question to ask. However, Naiim #33’s point stands – it would be easier to show the answer was true in the specific case of the human brain, rather than in the general case.
Comment #37 December 12th, 2018 at 3:14 pm
Lou #36: Math problems at least have the advantage that, once you’d expanded the 1000-character sketch into an attempted full proof, there’d then be a mechanistic way to check whether you’d succeeded or not.
Comment #38 December 12th, 2018 at 3:29 pm
Matt #20 and 22: you’d claim it through a network of foundations /shell companies headed by lawyers and agents who can keep you anonymous, making sure to buy the ticket in states that have laws that allow the most protections for winners. The genie can add enough to make this go from high probability of success to near-certainty. Upon a bit of reflection, having 83 100M jackpots in a row claimed by anonymous people seems likely to draw suspicion (although a good number of those will have multiple winners and those others will be public in many cases). This could suggest a plan of giving people winning tickets, or perhaps buying multiple copies of the winning ticket in multiple states and giving a few away. This is what comes to mind with just a bit of thinking, an oracle could do much better (advise which lawyers won’t betray me, etc)
It’s probably optimal to make the first question include only 5 winning numbers and use the rest of the space to give as much plan as possible if you only have one question.
The evidence is just buying the tickets, then waiting for the numbers to be announced. If we can ask for the “current location of the Ark of the Covenant” and evidence requires us to go dig, we can ask for some numbers and wait for the evidence to be revealed
Comment #39 December 12th, 2018 at 5:30 pm
Scott #35: “Yes, I think that elucidating exactly how the Biblical stories arose is one of the great research projects for the archeology and history of Western civilization, and that even a hardcore atheist should have little problem agreeing to that claim. (Questions surrounding Homer and Shakespeare are not far behind.)”
I’m mildly annoyed at your focus on Western civilization, so I’d like to propose some additional archaeological questions: Where do we find more Mayan codices? (This one is vaguer,) where do we find more reliable information about the life and teachings of Siddhartha Gautama (aka Buddha)?
Comment #40 December 12th, 2018 at 5:56 pm
I don’t know how to formulate this question well enough, but it would be related to the tension between the obvious lack of agency/free will (as defined, say, in TGitQTM), basically implying that humans are just artifacts of nature, like, say, solar flares or stalactites, and the equally obvious technological artifacts of agency, like spacecraft and buildings, that look not nearly as “natural” as solar flares or stalactites. Or maybe it should be an “ask Scott” question. Or even “already answered by Scott”.
Comment #41 December 12th, 2018 at 5:57 pm
Itai #39: Or what about more khipus?
With New World archeology in particular, what’s so frustrating and depressing is that (unlike with the Ark, or records of the Exodus) we know exactly when, how, and why the records were lost: the Spanish burned them.
Comment #42 December 12th, 2018 at 9:27 pm
Lou #30 and Naiim #33, genie answer:
“What is temporal perception and temporal action? Look to cognitive science and the principle of ‘predictive coding’, then generalize that principle! Consider the principle of ‘balance’ and the ‘golden mean’ and ask what happens when high-level (abstract) representations are integrated with low-level (concrete) representations. Relate planning to temporal perception. When we plan, how do we reason about cause-and-effect, imagine alternative possibilities and ask what *could* have happened? How do the 3 components of subjective time division (future,past and present) relate to perception and action?” (611 characters)
Comment #43 December 12th, 2018 at 11:27 pm
Hey genie, what is the question that you do not know the answer by far? Why?. Again. What is the question that you have more doubts in the answer? Why?. Hey genie, explain the mathematical theorem and its proof which is beyond of the understanding of any human of XXI and XXII centuries?. Genie, how can we create a computational and extremely realistic big bang with high likelihood to generate conscious life?. Can we obtain same benefit of this experiment?.
Comment #44 December 13th, 2018 at 2:06 am
Mark #43: Some of those seem impossible to verify almost by construction, and hence outside the scope of this exercise.
Comment #45 December 13th, 2018 at 4:43 am
Do we get to ask multiple questions? I’m assuming we didn’t
1. Is a fast takeoff likely with our tools anytime in the next century?
2. Which moral theory/ideaology/religion etc. would provided the greatest maximisation of humanities preferences if accepted?
3. What single action would result in the greatest preference maximisation for our reality?
4. Does any computable model exist that perfectly predicts the behaviour of the universe?
5. Vim or Emacs?
6. What way of thinking would lead to the most robust solution for the value-alignment problem?
7. Which book would I personally rate higher than any other by the end of my life, provided I do not break down mentally?
Oh, by the way Scott, do you know of any interesting research directions in Adiabatic Quantum Computing? Maybe something you’d like investigated?
Comment #46 December 13th, 2018 at 7:49 am
I think it would be interesting to ask questions of the form, “What is (a sketch of) a formulation / proof / explanation of [something] that is simpler than [some measurement of complexity]?”
This would help us get a better understanding of many things we might already know. For example, it could provide us with simpler or more elegant formulations of the known laws of physics, proofs from “the book” of various math theorems, physical phenomena, etc.
In particular, by repeatedly making [some way of measuring complexity] smaller, we could learn the simplest way of formulating the known laws of physics (perhaps in the process also providing us with a description or clue into physics we don’t yet know).
Comment #47 December 13th, 2018 at 12:49 pm
Where is my other blue and white sock?
Comment #48 December 13th, 2018 at 1:23 pm
I could tell him a particular sum of my money that I want to risk, the time span I want the returns in (eg. four years), a lower bound on how much money I want to earn from the investment, and an upper bound on how much of my own time I want to devote into doing the required work. This is a rather open-ended question, because the genie could give me lottery numbers for almost any lottery I can buy, or stock exchange tips, or even a hot tip I should sell to a pharmaceutical research company to jump to an incredible breakthrough, or anything else. There’s a lot of advice the genie could give me that fits in 1000 characters.
Or I could break most examples of private key cryptography.
Comment #49 December 13th, 2018 at 2:39 pm
Thank you for the link to the interview with Susskind. It’s indeed really interesting.
Comment #50 December 13th, 2018 at 3:33 pm
Is asking for answers to future questions allowed?
The answers to next year’s questions can be efficiently verified today, right? I mean, it only takes a constant amount of time for the year to elapse, and by definition the genie only replies with verifiable answers.
Assuming it doesn’t get asked an unreasonable number of questions. And no free will either.
Not that you can do much with a set of answers for which you don’t know the questions.
I guess you could just impersonate the genie. Maybe it was always an impersonator to begin with.
It’s a scam. The genie’s probably harvesting your email addresses and selling them. Don’t fall for it.
Comment #51 December 13th, 2018 at 4:03 pm
> Here I don’t mean NP in the technical sense (that would just be a pared-down version of the halting genie discussed above), but in the human sense.
Oh for a minute I thought you meant human-type questions (the scientific and math ones proposed weren’t that much different from technical NP). And I wondered how much evidence would really help.
Human: “Genie, was Bush 41 a war criminal?” Genie: “Yes, evidence is all in there, meticulously documented, here is a handy list of page numbers” (points to a five-foot stack of Noam Chomsky books). Human: Uh, thanks Genie, but nobody actually cares that much about evidence, it seems.
Similarly global warming and so on. Oh well.
Comment #52 December 13th, 2018 at 4:43 pm
Easily verifiable… that’s tough.
What is the smallest Turing Machine (smallest = states+symbols+input tape complexity), if any, that will compute the entire history of our universe?
I don’t actually think an answer would be easily verifiable, but if you got an actual TM setup, it would be a fun program to run to see if you could decipher anything in that mess that resembled our current physics or universe.
(My question probably isn’t even well defined, especially with that reference to “input tape complexity” thrown in there, but I assume this omniscient being will get the gist of my question, won’t zap me for the mistake, and will return a satisfiable answer to a slightly amended version of my question.)
Comment #53 December 13th, 2018 at 6:12 pm
Ever since I learned about NP, the main question I’ve contemplated asking such a genie would be “what, if anything, would I have to say or show to person X to convince them of Y?”
Comment #54 December 13th, 2018 at 6:12 pm
Algon33 #45: you’re asking the wrong genie, I’m afraid.
Comment #55 December 13th, 2018 at 6:43 pm
“Where, if anywhere, can we find intact DNA of non-avian dinosaurs?”
Unless I’m missing some background information, this question might not be worth asking, unfortunately.
https://www.nature.com/news/dna-has-a-521-year-half-life-1.11555
Comment #56 December 14th, 2018 at 1:50 am
Jon K. #52: Again, that one is definitely not easily verifiable, so the genie won’t answer.
Ok, I’ve got a question that doesn’t involve making mathematical proofs, forging cryptographically secure signatures, or gaining wealth. I’ll ask the genie to produce better poetry than any human can. The verification procedure is to submit the genie’s poetry to a publisher under a penname. Read what literary critiques say five years later about that penname. If they claim that the penname’s poetry represents a revolutionary jump in literature comparable to what Babits was, then the genie’s answer is accepted. I think if I ask this from the genie, it will find me an answer that no human poet of this century could find.
Comment #57 December 14th, 2018 at 1:59 am
And taking that train of thought further, on the next level of the polynomial genie hierarchy, there’s a genie who can not only give me good poetry but give me the best poetry ever, who can not only give a proof to P!=NP but the most elegant proof, and who can not only give me a tip to get rich but the tip to get the richest.
Comment #58 December 14th, 2018 at 3:29 am
I’d ask for instructions for making human eggs from skin cells. It’s been done in mice and there is some progress towards it in humans, so even though 1000 characters isn’t much to work with, it might be enough to give today’s researchers the key ideas.
That would move reproductive technology ahead by 10-20 years, with the following useful effects:
– Millions of women (yearly) are spared the hormone treatments currently required for egg harvesting
– More embryos become available for IVF, making preimplantation genetic diagnosis (PGD) more effective
– With IVF less onerous and PGD more effective, uptake of PGD dramatically increases
– Embryo editing becomes a viable medical procedure, unlike today
– Iterated embryo selection becomes theoretically possible
Comment #59 December 14th, 2018 at 3:33 am
Oh drat, I totally forgot about the stipulation that the genie’s hint must be (0) 1000 characters of (1) plain (2) English text. That dashes my hopes for the awesome poetry volume three times in one line.
In revenge, I’m forced to use your own words against you, Scott. I claim that the genie also can’t give a P!=NP proof then.
You’ve stated that there’s no trivial counting argument that will solve P!=NP, that the proof must use an entirely revolutionary new idea. You’ve also said that you’re tired of looking at every supposed P!=NP proof that some crackpot puts up on the internet, and that if someone believes that they have a P!=NP proof, they should write a properly formatted full article about that proof, submit it to peer-reviewed journal, and that when the mathematician community in general seems to accept the proof, then you’ll take a look at it. If the genie could give me 100000 characters, then it could dictate the full publishable journal article, one where the reviewers won’t even find the mistakes, that one is clearly verifiable. But from a 10000 character hint, I wouldn’t be able to reconstruct the proof, so in consequence the genie can’t give that hint either.
There’s a workaround of course. For the first question, I’ll ask for a thousand character long plain English text that has all zero digest in each of SHA-256, Snuffle 2008, and SHA3-256. That one is easily verifiable, and almost certainly exists, so the genie can provide it to me. I’ll publish that and say that the results come from a genie. Such a cryptography break is so remarkable that people will believe me and know that I have something very unusual. The person who steals the genie from me will then ask it for a P!=NP proof hint, and publish it with the claim that it came from the genie. Since people know that the genie is capable of such a thing, a complexity theory researcher will then know that the hint is worth investigating, and spend fifteen years of their life to understand the hint and produce the full proof. They will claim afterwards that the proof follows trivially from the genie’s hint.
Comment #60 December 14th, 2018 at 11:29 am
I would ask the genie how it works assuming it is explainable.
Also what is the correct interpretation of quantum mechanics. Bonus points if it answers “shut up and calculate”.
More generally a genie that would answer intractible religious debates. Of course even the knowledge of the correct answer likely wouldn’t resolve all debates.
Comment #61 December 14th, 2018 at 12:38 pm
I suspect the genie has only limited utility in math and science, likely saving only 50 years or so, since even to be able to verify a result you need a good chunk of the technology needed to discover it. Suppose, for example, you asked in 1900 about the memory molecule of biology. The genie could tell you about the helical structure of DNA, (which we found in 1953) but to verify it you need X-ray crystallography (starting 1912). Likewise a sketch of a proof of Fermat’s last theorem likely requires math from the mid-20th century. Verifying a genie-described exoplanet needs fancy telescopes and high speed light detectors, and so on.
So the true utility would be in problems with low tech and huge search spaces. If you want evidence from Biblical times, the only tool you need is a shovel, but you need to know where to dig. So if you have only limited queries, perhaps concentrate on these.
Comment #62 December 14th, 2018 at 1:41 pm
Inspired by the Mythbusters: Ask about historical technologies. They can be answered with a set of blueprints, and verified by trying to build it. Things like “How were the pyramids built?” or “What’s the recipe for Greek Fire?” Or maybe “Which of Da Vinci’s inventions would have worked?”
(The Mythbusters have already picked some of the low hanging fruit in this department, like Archimedes’ solar death ray, but there’s still plenty more.)
You may have to work to fit the blueprints within the 1000-character limit, but given that historians have already tried to replicate a lot of these things, the genie might just need to give us a few pointers to pin things down.
Comment #63 December 14th, 2018 at 2:27 pm
Genie, what is the most difficult question you can answer?
Comment #64 December 14th, 2018 at 3:09 pm
Modification to discipline people:
The genie throws a (hidden) coin. If it lands heads, and the request is fulfillable, then we get the correct answer. If it lands tails, or the request is impossible, then the genie may lie to us. Also, we get only a few questions (or a single one, no gaming of bounded probability error into exponentially small probability error).
This ensures that, when considering what to ask, we really think about how we could verify the answer, and not about what the genie considers “verifiable”.
Comment #65 December 14th, 2018 at 3:22 pm
James #63: Attempted revision of your question:
What’s the hardest question you can answer for which the answer is verifiable, and for which it’s also verifiable that the question is the hardest you can answer for which the answer is verifiable, and for which… oh, shoot… 😀
Comment #66 December 14th, 2018 at 4:12 pm
#65
I was distracted around the time of clicking submit.
But really would it loop? Would it burn up like Robby the Robot when ordered to kill?
What if we tell the genie that a good approximation is acceptable?
Comment #67 December 14th, 2018 at 4:21 pm
James #66: There’s no point in asking whether the genie would burn up / enter an infinite loop, if we can’t even figure out how to phrase our own question in a finitary way… 🙂
Comment #68 December 14th, 2018 at 6:53 pm
What’s the most important named theorem in ZFC that is true but isn’t provable?
Not completely sure of the phraseology of this, but I hope the genie gets the idea
Comment #69 December 14th, 2018 at 7:17 pm
I imagine there is a problem with this logic but …
There is a finite amount of verifiable knowledge that consists of a finite number of facts.
An answer would be a fact or a combination of facts.
There would be finite number of answers since they consist of a finite number of facts.
There would, hence (I think), be a finite number of questions to match to the answers.
So couldn’t the Genie assemble all of the answers, match the associated question to each of the answers and rate the difficulty of the question based upon some criteria, for example number of facts required for the answer.
Comment #70 December 14th, 2018 at 8:06 pm
K Arthur #68: If it’s not provable in ZFC, then it’s not a theorem of ZFC. Presumably you meant a sentence expressible in the language of ZFC?
But once again, this flagrantly ignores the rule about the genie’s answer being independently verifiable—in this case, almost by definition!
Comment #71 December 15th, 2018 at 9:00 am
Genie, of all answer you could provide, please tell me one I will consider in ten years as the most important information I’ve heard in my life.
(shamelessly forked from James Cross)
Comment #72 December 15th, 2018 at 9:08 am
PS: the question might well be: “Is it possible, beside speed, to significantly improve human intelligence?”.
Comment #73 December 15th, 2018 at 10:21 am
Actual experiment.
Me: Alexa, what is the most difficult you can answer?
Alexa: I’m not sure.
🙂
Comment #74 December 15th, 2018 at 2:34 pm
What do you think about the following announcement, which I think was discussed at the Q2B conference: “IonQ harnesses single-atom qubits to build the world’s most powerful quantum computer”
Comment #75 December 15th, 2018 at 4:16 pm
Mike #74: That’s clearly fine as a statement of what they hope and wish to do, and clearly misleading/hyperbolic if interpreted as a statement about anything they’ve already done (at least, anything that I know about).
Comment #76 December 15th, 2018 at 4:59 pm
Can we ask what substances we should try to cure cancer with?
Regarding the Biblical stories I agree that it would be interesting to know more how they arose, but I think it would be even more interesting to understand how Christianity came be become so broadly accepted.
Comment #77 December 15th, 2018 at 7:09 pm
I don’t know how I forgot the greatest verifiable mystery of all: who is Satoshi, and what’s the proof? (In that instance, there might literally be an NP-witness, in the form of a decrypt.)
Comment #78 December 15th, 2018 at 7:12 pm
I’ll probably close down this thread tomorrow. My fear was that everyone had already thought about what I’m calling NP-genies, so that I’d have to add some more constraints to make it interesting. But what happened, instead, was that commenter after commenter just ignored the crucial verifiability aspect—i.e., the one constraint that there was—and treated it as an arbitrary question-answering genie.
Comment #79 December 15th, 2018 at 9:09 pm
Does the genie’s answer (in the case where you get one) to “Genie, what can I tweet to @RealDonaldTrump to get him to resign?” count as being verifiable? I.e. you can post the tweet and see if it works…
Comment #80 December 15th, 2018 at 9:50 pm
Scott #70,
We can still repair that a bit: “What’s the most important named conjecture which is undecidable in ZFC and its undecidability in ZFC is provable in ZFC + a large cardinal axiom for some large cardinal axiom that is in the literature.” More work on defining “important” might be necessary.
Comment #81 December 15th, 2018 at 10:00 pm
Re: Jr # 76
Christianity promises resurrection, which is regarded with favor.
Comment #82 December 16th, 2018 at 4:57 am
Actually I would not ask about Jesus simply because the chance of their being any sort of physical evidence, or any other undiscovered evidence, of his life is small even if he did exist. (Which I definitely feel he did.) Learning that there was none would thus tell us nothing.
I would rather ask about evidence of the development of Greek mathematics. That truly is something hugely important for world civilization. Finding about more of pre-Euclid mathematics would be great, for example, or indeed about Euclid himself.
Comment #83 December 16th, 2018 at 5:36 am
The interesting thing about the NP-genie thought experiment is that getting a “No” answer is entirely unhelpful, because it doesn’t come with a certificate. So the interesting thing is to think about a question where you’re pretty sure the answer is “Yes” and what you really care about is the certificate.
Comment #84 December 16th, 2018 at 6:40 am
Malcolm #83: Right! A “no” answer does tell you that no witness exists, which is important information that you might never be able to obtain otherwise. But a “yes” answer provides more obvious benefits.
Comment #85 December 16th, 2018 at 6:42 am
asdf #79: That’s my favorite one so far! I think you win the thread.
Comment #86 December 16th, 2018 at 8:18 pm
I don’t think such a genie can exist, as stated. It is supposed to provide “ordinary evidence that, once you know where to find it, makes the answer to the question clear to every competent person who examines the evidence, with no further need to trust the genie”. But that depends on the experience of the questioner. If I ask “Genie, can you square the circle with a ruler and compass?”, the genie might answer with “No, since Pi is transcendental, and a ruler and compass can only construct algebraic numbers”. That’s a perfectly good answer today, convincing to “any competent person”. But if Archimedes had asked the same question (and he was clearly competent at mathematics) , it’s not at all obvious the genie could have provided him an answer both understandable and convincing.
So I think the genie has to take two arguments, the question and the current state of the art, and replies with a certificate the questioner can understand, if possible. This makes a “no” answer much less useful, since it means either no certificate exists, or a certificate exists but you won’t understand it. The genie cannot resolve this for you, since then it is not an NP genie but one of a more general and much more powerful kind.
Comment #87 December 16th, 2018 at 9:29 pm
Assuming the genie responds to all NP questions and only NP questions ask…
“What is an NP question that cannot be asked in less than 200 characters, and what is the answer to that question?”
The genie’s response itself allows the questioner to easily verify (by definition) that the question in the genie’s response cannot be asked in less than 200 characters, even though there is no understanding/verification of the question at the lower level… but then you run into Jerry’s Paradox because we somehow got the answer within the answer using less than 200 characters.
I think this kind of NP genie is really an oracle in disguise.
Comment #88 December 17th, 2018 at 10:09 am
Jerry’s Paradox #87: “No such question exists” would be a perfectly non-paradoxical answer in the example you gave.
And it’s not even the only non-paradoxical answer! The genie could just pick some question that takes more than 200 characters to specify, and answer it—that doesn’t imply that you yourself could have specified the same question using fewer than 200 characters. To force the answer “No such question exists,” you really want something like: “what is the lexicographically first NP question that can’t be asked in fewer than 200 characters, and its answer, and a proof of the answer, and a proof that nothing yielding the same answer can be asked in fewer than 200 characters and that the question is lexicographically first?”