{"id":4010,"date":"2018-12-11T13:44:43","date_gmt":"2018-12-11T19:44:43","guid":{"rendered":"https:\/\/scottaaronson.blog\/?p=4010"},"modified":"2018-12-17T21:41:09","modified_gmt":"2018-12-18T03:41:09","slug":"the-np-genie","status":"publish","type":"post","link":"https:\/\/scottaaronson.blog\/?p=4010","title":{"rendered":"The NP genie"},"content":{"rendered":"\n

Hi from the Q2B<\/a> conference!<\/p>\n

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.\u00a0 (Possibly subject to restrictions on the length or complexity of the question, to prevent glomming together every imaginable question.)\u00a0 What do you ask?<\/p>\n

(Standard joke: “What question should<\/em> I ask, oh wise master, and what is its answer?”\u00a0 “The question you should ask me is the one you just asked, and its answer is the one I am giving.”)<\/p>\n

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.\u00a0 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?\u00a0 Can you solve global warming with such an oracle?\u00a0 Cure cancer?<\/p>\n

But there are many other examples.\u00a0 Here’s one: suppose what pops out of your lamp is a genie for NP<\/em> questions.\u00a0 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.\u00a0 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.\u00a0 Or, of course, the genie could fail<\/em> to provide such evidence, which itself provides the valuable information that there’s no such evidence out there.<\/p>\n

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.<\/p>\n

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.\u00a0 Here are the candidates for NP questions that I came up with after about 20 seconds of contemplation:<\/p>\n