Introduction
This article lays the groundwork for a new field of theoretical Computer Science, which we call Theory of Computational Perplexity. Computational Perplexity is the study of how much puzzlement is prompted by a computational task. It is strongly related to, albeit distinct from, computational complexity theory insofar as the existence of an efficient algorithm for a given problem does not imply that the working computer scientist will be any less perplexed by the aforementioned problem. In the present article we will introduce the main concepts and define the main perplexity classes, $\mathsf {Perp}$ and $\mathsf{NPerp}$. The first major open problem of the field, $\mathsf{Perp}=^?\mathsf{NPerp}$, will be formulated, hoping to pave the way to a new and fruitful avenue of research.
Some Perplexity Classes
Let us begin with a familiar example. Consider the problem which the snobs call Boolean satisfaction problem, and to which the connoisseurs refer as $\mathsf{SAT}$. In plain prose, for a formula of propositional logic, we ask whether there exists an assignment that satisfies it. From a computational perspective, this is perhaps the most well-known $\mathsf{NP}$-complete problem, i.e., an $\mathsf{NP}$ problem that is as hard as any other $\mathsf{NP}$ problem (i.e., $\mathsf{NP}$-hard and in $\mathsf{NP}$). Now, recall that a problem is in $\mathsf{NP}$ iff there exists a non-deterministic turing machine that solves it in polynomial time, or, alternatively, if a deterministic machine can check in polynomial time whether a candidate solution is correct. As far as Perplexity goes, on the other hand, we shall not focus on Turing Machines anymore. Perplexity is about humans, and deals with intimately human themes such as hope and despair, and it does so in a systematic and systematisable way. From now onwards, Turing machines will be replaced by something they will never be able to replace: the working computer scientist.
But then, how will we understand $\mathsf{SAT}$ from a perplexity-theoretic perspective? We begin by framing what computational perplexity is about:
Definition 1 (Computational Perplexity). Computational Perplexity is the study of how much puzzlement or confusion is caused by a computational problem to the working computer scientist.
Clearly, boolean satisfaction will not be as daunting for a human than for a machine. Trying out a bunch of truth tables cannot be so bad, can it. Therefore, intuitively, $\mathsf{SAT}$ should be classified as one of the least perplexing problems. Finding an independent set in an undirected graph ($\mathsf{INDSET}$), on the other hand, while being as computationally hard as $\mathsf{SAT}$ (they are both $\mathsf{NP}$-complete), is clearly more baffling than the latter. Not to mention Private-neighbour independent set, the version of $\mathsf{INDSET}$ in which no nodes of the independent set are adjacent to more than one node in the complement. Here, on top of the puzzlement for even understanding what this means, we add the confusion of why on earth someone called it $\mathsf{PNIS}$ without questioning its disastrous giggling potential among students, and, even if they are not willing to admit it, professors. This is to say, complexity and perplexity must have different classes, since provably equally hard problems are obviously not similarly puzzling. We now begin by introducing some core perplexity classes in a way that it adequately captures the present intuitions. To do so, we understand “unpacking a question” algorithmically: we read it, we understand each word, then each sentence, then sentence compunds linked by connectives, and then conjecture what possible solutions may look like.
Definition 2 (The class $\mathsf{Perp}$). A problem is in $\mathsf{Perp}$ if and only if there exists a working computer scientist who is puzzled by the question, but manages to understand it in polynomial time by deterministically unpacking it in its elementary notions.
From the definition, $\mathsf{SAT}$ is clearly in $\mathsf{Perp}$: understanding what “finding an assignment that makes $\varphi$ true” once we are given $\varphi$ is a task that is cearly understood in polynomial time (the obvious proof is left to the reader). $\mathsf{INDSET}$, on the other hand, is a beast of a different breed. We read the question, and, not without feeling a bit of shame, we recall by drawing on a piece of paper the difference between a directed and an undirected graph. After some (hopefully short) trial-and-error, we try to make sense what an independent set is. We read the definition, and colour some nodes to see if we understood it. No, we have not. Reread, retry, erase, make a more general drawing, recolour some nodes, yes, these form an independent set, the definition makes sense. This process exhibits an exquisitely non-deterministic behaviour. Thus, we define the following class:
Definition 3 (The class $\mathsf{NPerp}$). A problem is in $\mathsf{NPerp}$ if and only if there exists a working computer scientist who is puzzled by the question, but manages to understand it in polynomial time by nondeterministically unpacking it in its elementary notions.
Alternatively, we can rephrase it as follows:
Definition 4 (The class $\mathsf{NPerp}$, alternative definition). A problem is in $\mathsf{NPerp}$ if and only if there exists a working computer scientist who is puzzled by the question, but manages to check in polynomial time if a candidate explanation is sensibly correct, by deterministically unpacking it in its elementary notions.
The existence of $\mathsf{NPerp}$ problems is clearly witnessed by $\mathsf{INDSET}$. ## An Open Problem
But can we be sure that $\mathsf{Perp}$ and $\mathsf{NPerp}$ are not identical? And what would their equivalence imply? As in the familiar case of $\mathsf{P}$ and $\mathsf{NP}$, we can easily see that we can obtain an inculsion $\mathsf{Perp}\subseteq \mathsf{NPerp}$. This is particularly evident if we consider the alternative deifnition, where the candidate interpertation of the question of what satisfiability is is the only possible one. But how about the other inclusion? I claim that understanding it may be as puzzling as it is hard to prove $\mathsf{NP}\subseteq \mathsf{P}$. Suppose however that we understand it, and we manage to show that $\mathsf{NPerp}\subseteq \mathsf{Perp}$, thus obtaining $\mathsf{Perp}= \mathsf{NPerp}$. The consequences for the practice of computer science, I contend, would be disastrous. If anything, the working computer scientist will not be anymore entitled to whine about how weird or confusing computational task are, since they will now that there is an efficient way to understand what they mean. The comforting conclusion “understanding this issue is left for future research” will be followed by sceptical glares of colleagues who will ask “but did you really think hard enough?”. As of now, however, I indulge in such privilege, maybe for the last time. Understanding what $\mathsf{NPerp}\subseteq \mathsf{Perp}$ means is a task that must be taken up in the years to come.