Is Humor Truly AI-complete

We recently posted a piece Kristine researched on Computational Humor. As she mentioned, some researchers consider the idea of a machine creating humor to be in a class known as AI-Complete. AI-Complete is defined to be the set of problems, tasks, games, behaviors, etc., for which if you develop a machine that can perform one of these tasks, it can likely perform all of them with a practical amount of tinkering.

This definition is inspired by the idea of NP-Complete from computatonal theory. The next few paragraphs will be a crash course in computational theory.

When studying algorithms, one would like to know how the run time of the algorithm changes as it's input size grows. Let's say your job involved assembling widgets into structures. The procedure you follow is your algorithm. Let's assume your career has been assembling structures that always have 5 widgets, and it takes you 10 minutes per structure.

After a while, you're promoted and now asked to make structures built from 10 widgets. These are more complex, it's going to take you longer to assemble. How much longer? Let's assume a 10 widget structure takes 20 minutes, and a 20 widget structure takes 40 minutes. A pattern emerges. It would seem your procedure runs in linear time. Double the number of widgets, double the time to assemble.

Solutions to problems people find interesting are often slower than linear. What if 5 widgets took 10 minutes, 10 took 25 minutes, and 20 took 85 minutes. It seems your runtime is dictated by the formula $y = \frac{1}{5}\cdot n^2 + 5$ . Broadly, we describe this problem as polynomial run time, since we have an $n^k$ involved, $k=2$ in this case. Yes, $k=3$ would be an asymptotic runtime. But humor me for now and just accept that we're going to group any $n^k$ runtime into the same group. If you're not comfortable with that, go read Sipser's book and come back later.

Computer scientists started to notice that some problems seemed to have no known polynomial time algorithms. An example is the traveling salesman problem - try to find the shortest route that visits a set of cities without visiting the same city twice. Some special cases are easy. For example, if every city has exactly two highways in and out of town. On small input sizes (perhaps 5-10 cities) human beings can seem to intuitively find the shortest routes very quickly. Yet, that intuition does not scale. As the input size increases, it seems there are no efficient algorithms, requiring brute force be involved.

It's important to note date we don't know for sure that no efficient algorithms exist. This is essentially, the famous $P \stackrel{?}{=} NP$ problem.

These problems that seem to require some brute force in this way are called $NP$ . The $NP$ stands for non-deterministic polynomial time. Not a great name, I know. Essentially, a problem is in $NP$ if finding a solution is very difficult (cannot be done in polynomial time), but giving someone a solution and asking them to verify it can be done in polynomial time.

It's not impossible that someone will eventually publish a result showing an efficient algorithm for solving any example of the traveling salesman problem in polynomial time. But as of yet, no one has identified such an algorithm. In fact, there's a somewhat surprising absence of any such algorithm. That's not proof one doesn't exist, however. Maybe every human who has ever looked at this problem is simply not clever enough.

While trying and failing to prove whether $P=NP$ or $P \subsetneq NP$ , computer scientists started trying to frame the problem in other ways. They noticed that many of these $NP$ problems had a certain interchangeable quality. Essentially, if you can solve one, you can solve them all. I'm sweeping a lot under the rug here. For slightly more on this, work your way through the verifier-based definition of NP-Complete. For the complete treatment of the forefront of human knowledge on the subject, sit back and enjoy the wonderful 116 page survey on NP-Complete put together by Scott Aaronson.

For our purposes in this post, it's enough to understand that there exist hard problems for which there are no known efficient algorithms to solve them - class $NP$ , and many of these problems have been shown to have an equivalence such that solving one, makes it easy to use that solution to solve the others.

The definition of the class of NP-complete algorithms is very well specified. Proving membership in it requires a formal proof in which you provide a polynomial time reduction between the proposed new member and an existing member. Essentially, the proof is of this form: Problem $A \in NP-complete$ . If you could solve Problem $B$ in polynomial time, then there is also a polynomial reduction that translates problems from $A$ to $B$ . While there might be a little overhead, essentially, $B$ would then be this helpful tool that just needs a few adapters to also work easily on other problems.

All of that says nothing about whether or not problems in $NP-complete$ are in fact not solvable in polynomial time. Remember, it could just be that humans are not clever enough. However, we can establish that a large body of problems are all "at least as hard as each other". Solve one efficiently, and with a reasonable overhead, you can solve the all efficiently.

Although for the record, almost no one believes $P=NP$ . The consensus opinion, which I agree with, seems to be that $P \subsetneq NP$ . However, it is important to note that, even if it seems obvious to some that $P \subsetneq NP$ , we are unable to prove it!

Establishing the class NP-complete exists and showing countless proofs that certain problems are members of this set is very rigorous. These proofs can be checked by others. Their rhetoric can be debated. All such proofs are believed to be mathematically correct.

The concept of AI-complete, on the other hand, is a much looser definition. It borrows the inspiration for it's name from the idea of NP-complete. In some sense, this is a nice parallel. It seems there are several seemingly different tasks which a machine could perform that would convince us that it has the capacity to also solve other intelligent problems.

For example, let's hypothesize that a piece of software is created which can read novels and then draft lengthy literary criticisms of those novels which are able to earn A grades in graduate level English courses. This would be a truly impressive feat! One might assume that the technology employed in creating such a piece of software could surely be re-purposed to create other very impressive results, even if the developers haven't yet gotten to anything beyond literary criticism.

Take a moment and think for yourself about what else you might attempt to do with the literary criticism writing software. Could it summarize the books rather than criticize them? Almost certainly. Could it generate new literary works? Seems likely. Could it accomplish any task you would expect an intelligent human being to be able to accomplish?

Hmm, that's a hard question. If you answered yes, then you believe this software is AI-complete, because it could be repurposed efficiently to perform other intelligent tasks. If you answered no, then you must consider literary criticism to be a lower level task not actually requiring any intelligence to accomplish.

So what sorts of activities are amongst the hardest things we humans use or intelligence to do? What about playing games? That depends on the game. I have a hard time believing an algorithm that can play tic-tac-toe would also be considered artificial intelligence by anyone's standards. For some time, many believed chess to be a sufficiently challenging problem. That is, until Deep Blue beat the world champion, yet seems unable to do anything else but play chess. More recently, AlphaGo beat the best human Go player. This is also a fantastic accomplishment, but it was achieved without anything we would regard as general artificial intelligence. I think it's safe to say that neither chess nor go are AI-complete tasks.

In his seminal work Computing Machinery and Intelligence, Alan Turing suggests that conversation is a task amongst the most difficult things humans do which requires our intelligence. I'll take for granted that the reader is familiar with the famous Turing Test.

I agree that conversation is in the "class" AI-complete. I'll even offer a pseudo-proof for you. In order to hold on a viable conversation, one must exhibit memory and show a capacity to learn. Without any memory, the artificial chatbot is quickly identified. Without the ability to learn, all conversations will stall out. That doesn't mean the ability to learn very difficult ideas quickly. Simply learning abstract ideas about one's conversation partner - their occupation, interests, relatives' names, hope, and dreams - are an impressive enough feat. If a machine can learn, however slowly, than it can be provided new knowledge. With the right teacher, even a slow learner can learn any concept. And a software agent can presumably learn at a fast rate and without getting tired or needing a break. Therefore, I assert that any artificial conversation agent with the ability to remember and learn should also have the capacity to be taught any other intelligent task.

I call the above a "pseudo-proof" because it's not rigorous. The logic seems to follow, but I haven't provided any polynomial time reduction demonstrating precisely how problems stated to one problem can be efficiently translated into problems from another problem. For this reason, the concept of AI-Complete sometimes makes me cringe. I find the lack of a formal definition can lead to mis-uses. Yet, I simultaneously agree with Turing, that conversation is in the "class" AI-complete.

But is the generation of humor in the class AI-complete? Can a machine write a joke?

Machines already have written jokes, though, not necessarily funny ones. Since humor is a subjective idea, it's rather difficult to discuss whether something is funny or not. Perhaps we can borrow further inspiration from computational theory and call the problem PAI-Complete, where the P stands for probabilistic. If the machine can make more than 50% of the people lack more than 50% of the time, then we accept the machine as successfully accomplishing the task of humor.

However, humor can sometimes arise from randomness. This is the basic idea behind MadLibs. In a MadLib, participants are asked to supply certain parts of speech, which are then injected into a secret text at pre-determined places. When all blanks are filled, the newly generated text is read out loud, and (sometimes) the words and phrases provided by participants can lead to a comedic result, entirely by chance. Can artificial intelligence emerge from an agent making decisions at random? If comedy can, but intelligence can't, then humor cannot be considered AI-Complete.

Admittedly, MadLibs are not celebrated as achievements in comedy. Awards are not issued for the best ones, and we have no celebrities known for their MadLib creations. The opposite is true of stand up comedy, a true art form.

The words a stand-up comedian uses are only part of their joke. Another aspect critical to humor is delivery. The manner in which the present it is often a carefully honed craft. Even the length of a pause can yield more or less laughter from an audience.

A good deal of stand-up comedy requires historical and/or cultural context to appreciate it. Further, many, but not all jokes, require to listener to make an inference based on the information provided to them. I have to admit, the manner in which our brains draw unstated conclusions and laugh when a surprising outcome is unexpectedly generated is a fascinating aspect of humor that might be worthy of being labeled AI-Complete.

Yet, for every celebrated comedic genius, there's dozens of jokes on gum wrappers, puns, and Family Circus which hardly elicit our higher level intellectual capabilities to parse.

Overall the concept of AI-Complete is a neat idea. However, I'm at a loss for what else to put into the class besides conversation / the Turing Test. There are certainly interesting aspects of some humor that belong, but I'm not sure how to separate humor into jokes which require generalized intelligence to understand and more crass chuckling.