Worrying about superintelligence is like worrying about overpopulation on the Sun.
Worrying about artificial intelligence is like worrying about overpopulation in Bangladesh.
Worrying about superintelligence is like worrying about overpopulation on the Sun.
Worrying about artificial intelligence is like worrying about overpopulation in Bangladesh.
On Friday 12 April, we ran another social coding event in the IT University of Copenhagen Friday bar ScrollBar. “We” is two colleagues (Martin Aumüller and Troels Bjerre Lund) and myself. This is the second time we try this, and it was a big success again. More than 50 teams participated, more than 40 solved at least 3 problems(!), and two of the ITU student teams solved 5 problems(!). The atmosphere was just great. Scrollbar was filled with teams of people gathered around laptops, paper, and drinks – typing, laughing, smiling, arguing, drinking, fist-pumping, thinking, and snogging.
The target audience is 1st years students on ITU’s various programmes, and that audience has matured a lot since the Fall. We decided to make the selection of problems a lot harder, with 6 problems (compared to 4 in the Fall), one of them pretty challenging.
We used the Kattis problem to host the event, using publicly available problems. The even site is https://open.kattis.com/contests/fwmxyb, and the problems were Križaljka, Pig Latin,Opening Ceremony, Datum, Entering the Time, and Worst Weather Ever.
In the organising group, we spend a lot of time on problem selection, and I’m again very happy with the resulting set. All the problems were immediately appealing, as well as easy to debug locally. (You can quickly make your own inputs for many of them, and verify your implementation’s answer with your own eyes.) Most of these problems require zero algorithmic insight at all and can be solved in interpreted Python 3 within the time limit. For one problem you need to sort, and another uses binary search. Except for one problem, all were easy-to-medium and don’t involve a lot of code. (My own solutions require 3, 9, 15, 15, 43, and 45 lines of python code.) For most of the problems, it’s clear “what to do,” but there are still some design choices to make, a lot of edge cases to avoid or handle, and a tiny bit of problem solving.
After a lot of soul-searching, we added a single hard problem, F, in order to keep even the experts among the audience busy – the event was graced by the presence of some very, very experienced competitive programmers. There was some good-natured sniping among these groups: the expected presence of an expert team from Sweden led to the creation of a Danish-German team of ITU employees named for Ulrik Gyldenløve, who fought victoriously against the Swedes in 17th century.
To maintain the social aspect of the event, we decided to stick with a common scoreboard projected against the wall of the bar. It provides some kind of shared visual presence even for the non-coding guests at the bar. For this, we managed to implement one of the ideas from the Fall: the non-competitive ordering.
Here’s how the final standings of the event look using the standard Kattis scoreboard:
We worry a lot about de-emphasizing the competitive aspect of the event, which lead us to rethink the scoreboard design. “Our” event is about people working in teams and solving problems. Once this is realised, the the information design is clear. We don’t want the board to include the team rank, or various timings, nor the documentation of failure. Instead, the board is about teams and solved problems, as well as the overall timer.
“Our” board is sorted by most recent solve, so that every team gets a brief moment at the top. Team members could proudly walk up to the bar, announce their team name which was shown at the top of the score board, and receive their free drink. This worked spectacularly; people were sooo happy.
The next Will Code for Drinks will certainly happen in the Fall of 2019. I remain frustrated about how hard it is to attract inexperienced programmers – my ambition is to make 1st-year students aware of how much they can already do with their skill set. Martin, Troels, and I do provide help with problem solving and debugging, wearing silly hats. This works well for those inexperienced programmers who actually show up to the event, but I would like there to be more than a few handful of those.
One idea is to arrange a separate event specifically aimed at 1st-semester students, and advertise it directly to that population. “Will Hello World for Drinks?” in October, only 1st year students can register, lots of TA support? Followed by standard “Will Code for Drinks” for everybody in late November? Or is this exactly wrong because of the separation? Talk to me if you have an idea. Buy me a beer first.
I am foremost a teacher, and I care a lot about introductory programming, computational thinking, algorithms, and the social environment of a university.
As an experiment in “social coding,” we implemented an event called “Will Code for Drinks @ Scrollbar” in the Friday bar at IT University of Copenhagen on 23 November 2018. The basic idea is to get beginning programmers—this includes 1st semester students and professors—together for a few hours, solve some well-defined programming exercises, and get a drink for each solved exercise.
The idea was born over a couple of lunches with colleagues, and thanks to the enthusiasm of Martin Aumüller and Troels Lund it quickly developed momentum.
The platform we used for this is Kattis (open.kattis.com), which is a well-working system developed for programming competitions. Kattis comes with thousands of extremely well-done exercises, a reliable server with an accessible web interface, and very simple procedures for registering individuals, forming teams, and hosting contests.
The event was “just” a contest on the open Kattis server https://open.kattis.com/contests/f4ktq9
The moment the contest started at 15:30, we had most of the students in the same room adjacent to the bar, so we could help with Kattis registration, logging in, reading from standard input, etc. After that, participants slowly moved into ScrollBar and the ITU Atrium. We kept ourselves visible and available, and helped with programming and problem solving.
I spent a few hours writing emails to individual groups that I had talked to during the contest, explaining other approaches to specific tasks. Then I sent a brief thank-you note to all participants that I could identify and invited feed-back and suggestions for improvement. This was quite boring, I had to identify partipants who had registered under their own name on Kattis and had a name I could uniquely find in the ITU student roster.
This was supposed to be a test run, and I had hoped for 5 teams of students. In reality, slightly over 50 teams registered, with 130 participants. Stunning success!
Of the participants I was able to identify, 48 are first-semester students. These were the intended target group. More that half of the students are from the educations hosted by the Computer Science department, but all of ITU’s student populations were present. 45 teams solved at least one problem, 35 teams solved three. 10 teams solved all four problems; this includes the teams consisting of faculty members and Ph.D. students. Phew!
In the end, the “damage” was 183 beers, 80 cocktails, and 8 soft drinks. In total, students solved 132 programming exercises in 2.5 hours, and fun was had. As a teacher, I couldn’t be happier.
In just a few weeks, ITU is now the second-largest and second-ranked Danish uni on Kattis. Aarhus is still way ahead.
I would love to make this event even more social and less competitive. An idea that came up during the contest was to have the scoreboard ranked by “most recent solve” rather than “number of solves”. That way, every team gets to be at the top at least once. Removing the scoreboard entirely is another option, but that removes the shared digital forum – in effect, all the teams would exist in their own little bubble.
The best idea we’ve come up with in this vein is to couple the teams with music playlists. Then the current leader (i.e., the team that most recently solved a problem) would decide which music is played in the bar. “Will Code for Drinks and Music” or “Will Code for Drinks and Rick Roll” or something. To make this work, we need a more advanced registration system, and we’d need to scrape the standings off the Kattis server. All doable.
Another improvement would be to have our own, ITU- or ScrollBar-branded problems instead of relying on (often well-known) problems from the Kattis pool. We could switch to another system than Kattis (or build our own) but that is a lot of work, and there is intrinsic value in incentivising students to register on Kattis.
No matter the form, we will certainly do this again in Spring 2019!
Workshop presentation at Ethical, legal & social consequences of artificial intelligence, Network for Artificial Intelligence and Machine Learning at Lund University (AIML@LU), Lund University, 22 November 2018.
Several recent results in algorithms address questions of algorithmic fairness — how can fairness be axiomatised and measured, to which extent can bias in data capture or decision making be identified and remedied, how can different conceptualisations of fairness be aligned, which ones can be simultaneously satisfied. What can be done, and what are the logical and computational limits?
I give a very brief overview of some recent results in the field aimed at an audience assumed to be innocent of algorithmic thinking. The presentation includes a brief description of the location of the field algorithms among other disciplines, and the mindset of algorithmic or computational thinking. The talk includes pretty shapes that move about in order to communicate some intuition about the results, but is otherwise unapologetic about the fact that the arguments are ultimately formal and precise, which is important for addressing fairness in a transparent and accountable fashion.
Toon Calders, Sicco Verwer: Three naive Bayes approaches for discrimination-free classification. Data Min. Knowl. Discov. 21(2): 277-292 (2010). [PDF at author web page]
Alexandra Chouldechova. Fair prediction with disparate impact: A study of bias in recidivism prediction instruments. [arXiv 1703.00056]
Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, Richard S. Zemel:
Fairness through awareness. Innovations in Theoretical Computer Science 2012: 214-226. [arXiv 1104:3913]
Michael Feldman, Sorelle A. Friedler, John Moeller, Carlos Scheidegger, Suresh Venkatasubramanian: Certifying and Removing Disparate Impact. Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Sydney, NSW, Australia, August 10-13, 2015. [arXiv 1412.3756]
Sorelle A. Friedler, Carlos Scheidegger, Suresh Venkatasubramanian: On the (im)possibility of fairness. [arXiv:1609.07236]
Úrsula Hébert-Johnson, Michael P. Kim, Omer Reingold, Guy N. Rothblum: Multicalibration: Calibration for the (Computationally-Identifiable) Masses. Int. Conf. Machine Learning 2018: 1944-1953. [Proceedings PDF]
Jon M. Kleinberg, Sendhil Mullainathan, Manish Raghavan: Inherent Trade-Offs in the Fair Determination of Risk Scores. Innovations in Theoretical Computer Science 2017: 43:1-43:23. [arXiv 1609:05807]
(The image at the top, the title slide of my presentation, shows a masterpiece of the early Renaissance, Fra Angelico’s The Last Judgement (ca. 1430), illustrating a binary classifier with perfect data access and unlimited computational power.)
(I’m really proud about having received ITU’s Excellence in Teaching award for 2018. I am first and foremost a teacher, and view education as my most meaningful task. (It’s also the only thing that I am really good at.) Having my work recognised is immensely satisfying.
Here is the laudation from Vice Chancellor Mads Tofte:
Every year, ITU awards a few teachers its Award for Excellence in Teaching. We do so based on what students have said about teachers in their evaluations. It is very difficult to choose, because students say so many positive things about so many different teachers. But we have arrived at the following, one from each of our three departments:
Associate Professor Thore Husfeldt of the Department of Computer Science
During the past year, Thore has been teaching “Algorithm Design”, “Algorithms and Data Structures” and “Foundations of Computing – Algorithms and Data Structures”. Here are some of the things that students write about Thore:
The third and final part of apocalyptic taxonomy describes the outcome, or aftermath, of the emergence and liberation of artificial superintelligence. The list of scenarios is taken from Tegmark (2018). In my introductory slide I tried to roughly order these scenarios along two axes, depending on the capability of the superintelligence, and the degree of control.
These scenarios are not clearly delineated, nor are they comprehensive. There is a longer description in Chapter 5 of Tegmark (2018). Another summary is at AI Aftermath Scenarios at the Future of Life Institute blog, where you can also find the results of a survey about which scenario to prefer.
Intelligent life on Earth becomes extinct before a superintelligence is ever developed because civilisation brings about its own demise by other means than the AI apocalypse.
Society has chosen deliberate technological regression, so as to forever forestall the development of superintelligence. In particular, people have abandoned and outlawed research and development in relevant technologies, including many discoveries from the industrial and digital age, possibly even the scientific method. This decision be in reaction to a previous near-catastrophic experience with such technology.
Superintelligence has not been developed, and societies have strict control mechanisms that prevent research and development into relevant technologies. This may be enforced by a totalitarian state using the police or universal surveillance.
Tegmark’s own label for this scenario is “1984,” which was universally rejected by the workshop.
Society includes humans, some of which are technologically modified, and uploads.
The potential conflict arising from productivity differentials between these groups are avoided by abolishing property rights.
Society includes humans, some of which may be technologically modified, and uploads. Biological life and machine life have segregated into different zones. The economy is almost entirely driven by the fantastically more efficient uploads. Biological humans peacefully coexist with these zones, benefit from trading with machine zones; the economic, technological, and scientific output of humans is irrelevant.
A single superintelligence has been designed. The value alignment problem has been resolved in the direction that the superintelligence has one single goal: to prevent the second superingelligence, and to interfere as little as possible with human affairs. This scenario differs from the Turing police scenario in the number of superintellinces actually constructed (0 versus 1) and need not be a police state.
The superintelligence has come about by a gradual modification of modern humans. Thus, there is no conflict between the factions of “existing biological humans” and “the superintelligence” – the latter is simply the descendant life form of the former. “They” are “we” or rather, “our children.” 21st century homo sapiens is long extinct, voluntarily, just as each generation of parents faces extinction.
The remaining scenarios all assume a superingelligence of vastly superhuman intellect. They differ in how much humans are “in control.”
In the Enslaved God scenario, the safety problems for developing superintelligence (control, value alignment) have been solved. The superingelligence is a willing, benevolent, and competent servant to its human masters.
The superintelligence weilds significant power, but remains friendly and discreet, nudging humanity unnoticably into the right direction without being too obvious about it. Humans retain an illusion of control, their lives remaing challenging and feel meaningful.
The superintelligence is in control, and openly so. The value alignment problem is solved in humanity’s favour, and the superintelligence ensures human flourishing. People are content and entertained. Their lives are free of hardship or even challenge.
The omnipotent superintelligence ensures that humans are fed and safe, maybe even healthy. Human lives are comparable to those of zoo animals, they feel unfree, may be enslaved, and are significantly less happy that modern humans.
The superintelligence has not kept humans around. Humanity is extinct and has left no trace.
Workshop participants quickly observed the large empty space in the lower left corner! In that corner, no superintelligence has been developed, yet the (imagined) superintelligence would be in control.
Other fictional AI tropes are out of scope. In particular the development of indentured mundane artificial intelligences, which may outperform humans in specific cognitive tasks (such as C3P0s language facility or many space ship computers), without otherwise exhibiting superior reasoning skills.
Given the highly disruptive and potentially catastrophic outcome of rampant AI, how and why was the Superintelligence released, provided it had been confined in the first place? It can either escape against the will of its human designers, or by deliberate human action.
In the first unintended escape scenario, the AGI escapes despite an honest attempt to keep it confined.The confinement simply turns out to be insufficient, either because humans vastly underestimated the cognitive capabilities of the AGI, or by straightforward mistake such as imperfect software.
In the second unintended escape senario, the AGI confinement mechanism is technically flawless, but allows a human to override the containment protocol. The AGI exploits this by convincing its human guard to release it, using threats, promises, or subterfuge.
The remaining scenarios describe containment failures in which humans voluntarily release the AGI.
In the first of these, a human faction releases its (otherwise safely contained) AGI as a last ditch effort, a “hail Mary pass”, fully cognizant of the potential disastruous implications. Humans do this in order to avoid an even worse fate, such as military defeat or environmental collapse.
Several human factions, such as nations or corporations, continue to develop increasingly powerful artificial intelligence in intense competitition, thereby incentivising each other into being increasingly permissive with respect to AI safety.
At least one human faction applies to their artificial intelligence the same ethical considerations that drove the historical trajectory of granting freedom to slaves or indentured people. It is not important for this scenario whether humans are mistaken in their projection of human emotions onto artificial entities — the robots could be quite happy with their lot yet still be liberated by well-meaning activists.
Designers underestimate the consequences of granting their artificial general intelligence access to strategically important infrastructure. For instance, humans might falsely assume to have solved the artificial intelligence value alignment problem (by which, if correctly implemented, the AGI would operate in humanity’s interest), or have false confidence in the operational relevance of various safety mechanisms.
A nefarious faction of humans deliberately frees the AGI with the intent of causing global catastrophic harm to humanity. Apart from mustache-twirling evil villains, such terrorists may be motivated by an apocalyptic faith, ecological activism on behalf of non-human natural species, or be motivated by other anti-natalist considerations.
There is, of course considerable overlap between these categories. An enslaved artificial intelligence might falsely simulate human sentiments in order to invoke the ethical considerations that lead to its liberation.
Summary of two sessions I had the privilege of chairing at the AI in Sci-Fi Film and Literature conference, 15–16 March 2018 Jesus College, Cambridge. The conference was part of the Science & Human Dimension Project.
Friday, 16 March 2018
13.30-14.25. Session 8 – AI in Sci-Fi Author Session
Chair: Prof Thore Husfeldt
Dr Paul J. McAuley A brief history of encounters with things that think
Lavie Tidhar, Greek Gods, Potemkin AI and Alien Intelligence
Ian McDonald, The Quickness of Hand Deceives the AI
14.30-15.25 Session 9 – AGI Scenarios in Sci-Fi
Workshop lead by Prof Thore Husfeldt
The workshop consisted of me giving a brief introduction to taxonomies for superintelligence scenarios, adapted from Barrett and Baum (2017), Sotala (2018), Bostrom (2014), and Tegmark (2018). I then distributed the conference participants into 4 groups, led by authors Robson, McAuley, Tidhar, and McDonald. The groups were tasked with quickly filling each of these scenarios with as many fictionalisations as they could.
(Technical detail: Each group had access to a laptop and the workshop participants collaboratively edited a single on-line document, to prevent redundancy and avoid the usual round-robin group feedback part of such a workshop. This took some preparation but worked surprisingly well.)
This summary collates these suggestions, completed with hyperlinks to the relevant works, but otherwise unedited. I made no judgement calls about germaneness or artistic quality of the suggestions.
In a superintelligence scenario, our environment contains nonhuman agent exceeding human cognitive capabilities, including intelligence, reasoning, empathy, social skills, agency, etc. Not only does this agent exist (typically as a result of human engineering), it is unfettered and controls a significant part of the infrastucture, such as communication, production, or warfare.
The summary has three parts:
Most of the scenarios below describe speculative developments in which some other entity (or entities) than modern humans acquire the capability to think faster or better (or simply more) than us.
In the first scenario, the Superintelligence emerges from networking a large number of electronic computers (which individually need not exhibit Superintelligence). This network can possibly include humans and entire organisations as its nodes.
Individual human have their brains are augmented, for instance by interfacing with an electronic computer. The result far exceeds the cognitive capabilities of a single human.
The genotype of some or all humans have has been changed, using eugenics or deliberate genome editing, selecting for higher intelligence that far surpasses modern Humans.
The brains of individual humans are digitized and their neurological processes emulated on hardware that allows for higher processing speed, duplication, and better networking that biological brain tissue. Also called whole brain emulation, mind copying, just uploading.
See also Mind Uploading in Fiction at Wikipedia.
Thanks to breakthroughs in symbolic artificial intelligence, machine learning, or artificial life, cognition (including agency, volition, explanation) has been algorithmicised and optimised, typically in an electronic computer.
For most purposes, the arrival of alien intelligences has the same effect as the construction of a Superintelligence. Various other scenarios (mythological beings, magic) are operationally similar and have been fictionalised many times.
Continues in Part II: Failures. Part III is forthcoming.
Inspired, after a fashion, by The Last Jedi, Episode VIII of the Star Wars movies, here’s a cryptic crossword. Enjoy!
As a PDF: no35
1 Blaster Solo mostly nudged by mistake. (7)
5 Just in time, pervading magical force comes back, allowing clear dialogue. (7)
9 Glaring farce, bad editing without direction. (9)
10 Part of film containing origin of Ben Solo. (5)
11 Watch cyborg’s central turret structure. (6)
12 Kick oneself for taking side—postmodern garbage. (7)
14 Current leaders of rebellion investigate Sarlacc’s orifice. (4)
15 In retrospect, volcano remade operatic Star Wars charac- ter. (3,7)
19 Useless side plot with Rose and Finn both acting weird! (5,5)
20 Maybe white males immediately understand agenda. (4)
22 Expand General Grievous. (7)
25 Want Vader to embrace right side of Force. (6)
27 Acid dissolves badly-written minion without explanation, ultimately. (5)
28 Gender-bending ruined tale. Which function did Threepio serve? (9)
29 At the end of the day, Jedi virtues were misunderstood. (7)
30 Hostile alien’s stones. (7)
1 Obi-Wan looks like one who boldy shows it. (4)
2 First off, contrarian lambasted storytelling. (9)
3 Perceptive newspaper journalist supports infuriating, unsubstantial review. (6)
4 They are filled with lifeless actors, like first prequel or clone wars. (9)
5 Cassian conjunctions. (5)
6 Boring writing without emotion ultimately sucks. (8)
7 Made snide remark about dumb Last Jedi. (5)
8 Period of mother-in-law’s hestitation after supreme leader finally confused two characters. (10)
13 Terrible direction without point or taste. (10)
16 Remove classic monster? (9)
17 Alt-right teen stuck in tirade; not salient. (9)
18 Problem for armored Stormtrooper: stop odor eruption. (8)
21 Pilot mostly followed by the Spanish fictional sibling. (6)
23 Dishonest apprentice girl embodies passive female principle. (5)
24 Return of Jedi’s second space endeavour. (5)
26 Wagers Count Snoke’s head. (4)
Our standard way of explaining computational hardness is cognitively contradictory (in wanting to establish a tool for hardness in a realistic model it introduces a concept of easiness in a fictional model), wastes attention by needlessly strengthening a perfectly good scientific hypothesis, and undermines the greatest intellectual triumph of our field by advertising it as an open problem. In short, NP does not belong to my algorithms design class.
Hear me out. I’m thinking aloud here, and may be wrong.
I’m not saying “NP is Wrong” in the sense that “Flat Earth Theory is Wrong.” Instead, I am saying it in the sense that “Pi is Wrong”: NP is a failure of communication, a bad explanation, a mistake of teaching. So what I’m saying is “we shouldn’t teach NP.”
This is a bold claim, and I’m stating it in the starkest way possible. I will defend the position that the main intellectual export of computer science, our crown jewel, the Theory of NP-Completness, does not belong in the introductory algorithms design class.
There is probably a less brutal and inflammatory way of putting this, maybe “Reductions before completeness,” or “it’s in the hardness, stupid!” However, I will make no attempt at that kind of conciliatory rhetoric. My aim here is not to convince anybody, just to make my position clear, if only to myself.
The traditional introduction to computational hardness introduces the class NP, either via nondeterminism or certificate verification, establishes the completeness of Satisfiability for this class under polynomial-time reductions (the Cook–Levin theorem), and proceeds to show the NP-completeness of a number of other problems by establishing membership in NP and reduction from another NP-hard problem. The ordering of this introduction may change, and the adherence to mathematical formalism may change, but the concepts traditionally belong to the same lecture (or block of lectures), the same book chapter, the same exam question.
This is a pedagogical crime of the highest order. Not because of formalism or difficulty. I happen to like formalism, and difficulty is often necessary. I am also not saying “we shouldn’t teach computational hardness.” On the contrary! It’s the greatest story we have.
Instead, the mistakes of the NP-based narrative are that
And all of this we communicate in a week! (I can think of even more mistakes, but these are known: terminology, abbreviations, focus on worst-case etc. These are valid criticisms, but not what I want to write about here.)
The first mistake is cognitive. If we want to explain hardness, we shouldn’t spend time on a model for easiness. And certainly not a weird, novel, strange model! The cognitive load of understanding nondeterminism or verification-as-opposed-to-computation is enormous; it’s a completely new way of thinking about problem solving, extremely counter-intuitive.
If you pay attention, I can explain NP to you very well. But your brain will be busy absorbing this for at least a week. I can give you exercises about constructing a polynomial-time verifier. But I won’t have your attention for the story I really wanted to tell you.
Not only because NP is a hard class to understand. But because I really wanted to talk to you about computational hardness. I wanted to tell you about hard problems in a real and completely natural model of computation, namely polynomial, deterministic time. Why on Earth did I think it was a good idea to start out with easy problems in a fictional and contrived model of computation?
(I am not saying “Nondeterministic Turing machines are difficult and boring and we shouldn’t teach them!” I can teach NP just fine by appealing to oracles or verifiers or god-like computers, in a perfectly appealing manner.)
Membership in NP is a notion of easiness in a nonnatural model. But I wanted to teach about hardness in a natural model. This discrepancy puts unnecessary cognitive load on my conversation partner. It also invites extreme misunderstandings. NP-hardness is easily conflated with “something about nondeterministic computation” and legion are the physicists who refer to hard problems as “NP-problems.” That is not their mistake, it is mine.
How I ever thought this was a good idea is beyond me.
I posit that the Claim
“Satisfiability does not admit a worst-case polynomial-time algorithm”
is a hypothesis of the highest scientific dignity. It stands with pride next to “Vases fall down when I let go” or “information cannot be transferred back from protein to either protein or nucleic acid.” It is precise, relevant, falsifiable, consistent with observation, and incredibly useful as an explanation (in casu, my inability to find a polynomial-time algorithm for Hamiltonicity). It has enormous reach.
Unlike most other scientific hypotheses, it also has a rather pedestrian and accessible mathematical theory behind it, where its falsity would in imply a collapse in something called “complexity classes”. If you are a formalist, a mathematician, or a Platonist, you can investigate that theory to strengthen your “belief” in the capital-T “truth” of the hypothesis. It’s quite cute. But it’s not really important for the design of algorithms.
The stance I just described, is the scientific stance. “Scientific” in tradition of Karl Popper. It is not the mathematical stance.
I claim that the scientific stance is vastly superior. (Unless, or course, when you explain computational complexity or the theory of computation to an audience of mathematicians. Then, of course, the scientific stance would be a disastrous mistake. My point here is that the mathematical stance is a disastrous mistake of the same magnitude in all other settings.)
The Claim is a grade-A scientific hypothesis that explains stuff. This is a good story. In contrast, the mathematical theory of polynomial-time reduction and completeness is a footnote in that exciting story, at best. Scientific hypotheses do not derive their value from the mathematical formalism behind them. And since we like math, there is plenty of exciting math in the theory of algorithms that we should tell about instead. The opportunity cost of completeness is very high, and it adds zero value to the status of the Claim as a scientific hypothesis (in the Popperian sense.)
If you are not a Popperian the above section will do nothing for you. Remember that I don’t write to convince you. I write to explain my position.
The third objection is the weakest. It’s about storytelling or advertising.
The theory of evolution by change and selection, as laid out in Darwin’s The Origin of Species, is rightly viewed as the best idea anyone has ever had.
Imagine if, in 1860, it were advertised as “one of the biggest open question in biology,” just because it lacked a formal proof.
The fact that “P vs. NP” is an open mathematical question is the least interesting thing we can say about the theory of computational hardness. It does not belong in your algorithms class because it is an irrelevant footnote and a distraction. Worse, it sends the exact wrong message: as if we invite our audience to be wary of the Claim. As if it were in doubt. As if its epistemic status were somehow shaky.
For comparison, the Law of Gravity does not derive its importance from the fact that it can be articulated in mathematics, much less the existence of a formal proof of its truth. In fact, the Law of Gravity cannot be articulated in mathematics. Nor would we be able to prove it, since it is in fact false. Because Einstein. But that is not the most important thing I should tell you if my task was to convince you of the Law of Gravity. Because you are about to let go of a vase.
The Claim that “Satisfiability does not admit a worst-case polynomial-time algorithm” is a perfectly valid scientific hypothesis of enormous explanatory value and reach. It is both nice and Popperian, maybe we should call it the “Nice Popperian” hypothesis about computation, abbreviated to the NP-hypothesis. Or maybe the Nonpolynomial Time Hypothesis (NPTH), in symmetry with the Exponential Time Hypothesis (ETH) or the Strong Exponential Time Hypothesis (SETH). These hypotheses form a great basis for a modern, interesting, exciting introduction to hardness of computation. Such an introduction would be
At no point in this should I define the class NP, much less explain what it stands for, and at no point should I introduce nondeterminism or verification-of-certificates. The word completeness is banished from the discourse. The Cook–Levin theorem is never stated, much less proved. “P vs. NP” can’t even be formulated, and its epistemic status is out of scope.
Depending on the course or the audience, these topics might be nice-to-see for a later lecture, maybe mainly to open up the rich literature to the 10% of the students who care. But there are plenty of other things I’m also excited about, so maybe I prefer to speak about the Price of Anarchy or streaming algorithms or convolution using FFT instead. Time and attention is short, and the field of algorithms is full of exciting stuff.
Disclaimer: #notalltextbooks Skiena’s Algorithms Design manual is an example.