So at this point, we have the tools to show that there are problems that are about as hard as each other, but we still don't know whether they have efficient algorithms or whether we should expect them to.
Ultimately, what we want to do is classify those problems that we know have efficient algorithms. But first, what is a problem? We have a vague notion of what this is, but we would like to formalize this notion. It might be surprising that we would want to formalize what a problem is mathematically or that we can even do this, but this is really what computer science is about: the mathematics of how to solve problems.
Recall that we mentioned that a decision problem is one that, when given an input, answers a Yes or no. This sounds suspiciously like a function, so we might say that a problem is some function that maps inputs from $\mathbb N$ to $\{Y,N\}$. But as we've seen above, our domains can get much more complicated than $\mathbb N$.
Viewing such problems as functions is a good start, but we want something more general to work with. In the above examples, there's no unification in terms of the number of inputs or the domains of the functions, which makes it a bit difficult to talk about the two questions in the same way.
One of the first insights you will have internalized already is that we can represent pretty much anything we would like with the proper encoding. Generally speaking, this means that we can treat any input as a string. We can even treat "multiple" inputs, as in the case of our graph problem, as a single string, by encoding the delimiters appropriately as well. In this way, we can now define decision problems a functions from strings to Yes or No.
Definition 19.1. Let $\Sigma$ be an alphabet. A decision problem is a Boolean function $P:\Sigma^* \to \{0,1\}$ that maps input strings over $\Sigma$ to a single bit.
Another way to look at a Boolean function is as a set $S$, where a string $x$ is in $S$ if $P(x) = 1$ and $x \not \in S$ if $P(x) = 0$.
Definition 19.2. Let $\Sigma$ be an alphabet. A decision problem is a set $P \subseteq \Sigma^*$. A string $x$ is a Yes instance of $P$ if and only if $x \in P$.
Then we can treat an algorithm as a function that tells us whether an input is a Yes or No instance and we can associate it with a running time.
Definition 19.3. An algorithm $A$ solves a problem $P$ if \[A(x) = \begin{cases} \mathrm{Yes} & \text{if $x \in P$,} \\ \mathrm{No} & \text{if $x \not \in P$.} \end{cases}\] We say $A$ runs in polynomial time if for every input string $x$, $A(x)$ terminates in $\leq p(|x|)$ steps, where $p$ is a polynomial.
This allows us to define a class of problems based on the time complexity of the algorithms that solve them.
Definitiom 19.4. The class $\mathbf P$ is the class of decision problems for which there exists a polynomial time algorithm.
What problems are in $\mathbf P$? Almost every problem we've seen so far is a problem in $\mathbf P$, because we have polynomial time algorithms that solve them (with a few exceptions). As a reminder, the following problems that we've seen that are in $\mathbf P$ are
However, we've also seen a few problems where we don't know whether there are polynomial time algorithms.
A big problem with this is that we don't know whether there is or isn't an efficient algorithm for these problems. As mentioned before, a definitive answer one way or the other would be helpful, but we don't have one. But maybe we can try something less ambitious first. What if, instead of trying to solve the problem, we could check whether a proposed solution is correct?
Imagine again that we have a mysterious cube that can solve a particularly difficult problem for us. A good question to ask about our mysterious cube is how we can tell if it's correct. If it can solve a hard problem, how can we possibly check it?
So the mysterious cube goes okay, I can give you proof and along with a Yes answer to the problem it prints out a receipt that we can use to check whether it's correct or not. And after being spooked by the cube that was apparently listening in on us, we have to figure out what to do with this new information.
Definition 19.5. An algorithm $V(x,c)$ is a verifier for a problem $P$ if for every input string $x$, $x \in P$ if and only if there exists a string $c$ such that $V(x,c) = yes$. We say that $c$ is a certificate.
Example 19.6. Consider the Independent Set problem. If a graph $G$ contains an independent set, a certificate for this is the set $S$. Given $S$, we can check if $S$ is an independent set in polynomial time: for each vertex in $S$, check its neighbours and verify that none of them are in $S$.
Of course, we can ask the same sorts of questions about verification algorithms as we do of any algorithm, particularly what its time complexity is. This leads us to the following idea.
Definition 19.7. The class $\mathbf{NP}$ is the class of decision problems for which there exists a polynomial time verifier $V$. That is, $V(x,c)$ is a polynomial-time algorithm and the certificate $c$ has size polynomial in the size of $x$; $|c| \leq p(|x|)$ for some polynomial $p$.
One thing you might notice is that $\mathbf{NP}$ is not exactly an acronym for polynomially verifiable. That is because efficient verification is an alternate, but equivalent, definition for $\mathbf{NP}$. $\mathbf{NP}$ actually stands for nondeterministic polynomial time. The original definition has to do with distinguishing between problems that could be solved on deterministic vs. nondeterministic Turing machines.
For our purposes, we can think of it this way: we can solve a problem in $\mathbf{NP}$ in polynomial time using nondeterminism. How do we do this? First, we nondeterministically guess/choose a certificate $c$. Since $c$ is polynomial in size, we can do this in polynomial time. Then once we have our string, we can run the verifier in polynomial time to get our answer.
It turns out that a lot of our difficult problems can be efficiently verified and so are in $\mathbf{NP}$. But we also have that any problem that was efficiently solvable to begin is also efficiently verifiable.
Proposition 19.8. $\mathbf{P} \subseteq \mathbf{NP}$.
Proof. Suppose we have a problem $P \in \mathbf P$. Then there is a polynomial time algorithm $A$ that solves it. We will define the following verifier $V$ for $P$:
\begin{algorithm}
\begin{algorithmic}
\PROCEDURE{V}{$x,c$}
\STATE run $A(x)$
\RETURN{whatever $A(x)$ returned}
\ENDPROCEDURE
\end{algorithmic}
\end{algorithm}
Essentially, this verifier ignores whatever certificate is provided and just computes the answer itself. This verifier runs in polynomial time, since $A$ runs in polynomial time. Therefore, $P \in \mathbf{NP}$. $$\tag*{$\Box$}$$
So the natural question to ask is: what about the problems that can be efficiently verified, but not efficiently solvable? What are those called? And the answer to that is, we don't know, because we don't know if any exist.
Problem 19.9. Does there exist a problem $P \in \mathbf{NP}$ such that $P \not \in \mathbf P$?
You may be more familiar with the following formulation of the problem:
Does $\mathbf P = \mathbf{NP}$?
This is the famous $\mathbf P$ vs. $\mathbf{NP}$ problem—the biggest open problem in theoretical computer science for almost 50 years. Practically speaking, it's the roadblock that keeps us from definitively answering whether large numbers of problems are efficiently solvable.
Philosophically, this question raises questions about how we think about computation and efficiency, and one of the Millennium Prize Problems. Intuitively, it should be much easier to verify a solution for a problem than it is to find it. And yet, we've been unable to prove it.
A lot of the computational complexity theory that has been developed since the early 70s was in the pursuit of this question. And if you ever go on to study more complexity theory, what you'll find are some answers and way more questions.
Recall that reduction is not symmetric. This suggests that one thing we could do is try to find the "hardest" problems in NP and try to separate those from the "easier" ones. But what does "hardest" mean in this context? That would be the existence of some problem $A$ for which $A \leq_P B$ for all $B \in NP$. Such problems are called NP-complete.
Definition 19.10. A problem $P$ is said to be $\mathbf{NP}$-complete if
If a problem $P$ satisfies (2), we say $P$ is $\mathbf{NP}$-hard.
It's important to note that a problem can be $\mathbf{NP}$-hard but not in $\mathbf{NP}$, which is why that notion is separate from the notion of completeness. Problems that are $\mathbf{NP}$-complete represent the "most difficult" problems in $\mathbf{NP}$.
One consequence of the existence of such a problem is it would give us a very easy way to show that $\mathbf{NP} = \mathbf P$. Suppose that $P$ is $\mathbf{NP}$-complete. If we find a polynomial time algorithm for $P$, then this means we have a polynomial time algorithm for every problem in $\mathbf{NP}$, by transitivity of $\leq_P$, and therefore $\mathbf P = \mathbf{NP}$.
Of course, an obvious question is whether such a problem exists. It sounds like a lot of work to show that a problem $P$ is $\mathbf{NP}$-complete, since one would have to show how to encode an arbitrary problem in $\mathbf{NP}$ into an instance of $P$ (how would this work for something like Vertex Cover?). But for now, let's suppose that there is an $\mathbf{NP}$-complete problem out there. By using transitivity of $\leq_P$, we get the following.
Proposition 19.11. Let $P$ be $\mathbf{NP}$-complete and suppose $P' \in \mathbf{NP}$. If $P \leq_P P'$ then $P'$ is $\mathbf{NP}$-complete.
Proof. Let $Q \in \mathbf{NP}$. Since $P$ is $\mathbf{NP}$-complete, we have $Q \leq_P P$. But since $P \leq_P P'$, by transitivity, we have $Q \leq_P P'$. Since $Q$ was arbitrary, we have that $P'$ is $\mathbf{NP}$-complete. $$\tag*{$\Box$}$$
So if we want to show that $P$ is $\mathbf{NP}$-complete, we can avoid having to show how to transform an instance of some arbitrary problem in $\mathbf{NP}$ into an instance of $P$. All we have to do is show that we can transform a problem we've already shown is $\mathbf{NP}$-complete into $P$, which is much easier. The other observation is that this means that all $\mathbf{NP}$-complete problems are polynomial time reducible to each other.
Of course, all of this only works if such a problem actually exists. That such a problem does exist was shown in 1971 by Stephen Cook, who we've seen before briefly when we were discussing fast integer multiplication. This is the result for which Cook is most famous. The theorem was independently proved by Leonid Levin, who at the time was in the Soviet Union. Levin is currently a faculty member at Boston University and Cook is a faculty member at the University of Toronto, which he joined in 1970 due to being denied tenure at Berkeley.
Theorem 19.12 (Cook-Levin). Satisfiability is $\mathbf{NP}$-complete.
We won't go through the proof in detail here, because it involves Turing machines, but the proof is really amazing. So recall that a Turing machine is a model of computation and for all intents and purposes, you can consider a specific Turing machine as a computational device that computes the solution to a particular problem, much like an algorithm. Here, we're particularly interested in nondeterministic Turing machines.
Since $\mathbf{NP}$ is the class of problems that can be solved by a nondeterministic Turing machine in polynomial time, an easy way to show that every problem reduces to a particular problem is just to show how to simulate a nondeterministic Turing machine. This is basically what the proof of Cook-Levin does.
The idea is to take a nondeterministic Turing machine and an input string and to show how to construct a propositional formula that simulates the computation of the Turing machine on the input string. The proof involves showing the following:
The consequence of this is that if we can solve Satisfiability, we can solve any problem in $\mathbf{NP}$. How? Here is an algorithm:
So if we can solve Satisfiability in polynomial time, we can solve any problem in $\mathbf{NP}$ in polynomial time.
The existence of an NP-complete problem was obviously a huge breakthrough and the natural follow-up question was what other NP-complete problems might be out there. Since these are the hardest problems in NP, the thinking was that we'd find a few more and it wouldn't be very long before we're able to show a clear separation from P. Not long after, Richard Karp (from Edmonds-Karp) published a paper showing 21 problems were NP-complete in 1972, some of which we've seen already. And since Cook-Levin and Karp, there have been thousands of problems shown to be $\mathbf{NP}$-complete.
This leads to another interesting question. We obviously have problems that are efficiently solvable. And we have a surprisingly large number of problems that are difficult, which are $\mathbf{NP}$-complete. In fact, most problems that we can show are in $\mathbf{NP}$ turn out to be either $\mathbf{NP}$-complete or actually in $\mathbf P$. But is there anything in between? More specifically, are there problems that are in $\mathbf{NP}$ but not $\mathbf{NP}$-complete? The answer, surprisingly, is we don't know! Part of the reason for this mystery is the following theorem of Ladner from 1975.
Theorem 19.13 (Ladner). Suppose that $\mathbf P \neq \mathbf{NP}$. Then there exists a problem $P \in \mathbf{NP} \setminus \mathbf P$ that is not $\mathbf{NP}$-complete.
So if we can show that there aren't any such problems that are "in between" $\mathbf P$ and $\mathbf{NP}$-complete, then we can show that $\mathbf P = \mathbf{NP}$. Of course, the issue is that we don't know for sure either way. We have some problems that we think might qualify, but we haven't been able to prove it definitively.
There are some particularly important problems that could exist in this space. The first is one Integer Factorization. The standard version of this problem is to find the prime factors of an integer $n$. The decision problem version is: Given an integer $n$ and an integer $m$ with $1 \lt m \lt n$, is $m$ a factor of $n$? Despite there being no efficient algorithms for solving Integer Factorization, no one has been able to show that it is $\mathbf{NP}$-complete. In fact, there's enough evidence that it's not completely crazy to think that Integer Factorization might turn out to be in $\mathbf P$. However, most people think this is a pretty good candidate for an intermediate problem.
The other big one is Graph Isomorphism: Given two graphs $G$ and $H$, are $G$ and $H$ isomorphic? We say two graphs are isomorphic if there's a way to map vertices of one to the other in such a way that the edge relationships are all preserved. In effect, an isomorphism is really a renaming of variables. Again, no one has been able to show that this problem has an efficient algorithm or that it's $\mathbf{NP}$-complete. The last big breakthrough on the problem was about five years ago, when Professor Babai, in our department, gave a quasipolynomial algorithm; i.e. it runs in $2^{O((\log n)^c)}$ time. Graph Isomorphism is a special case of Subgraph Isomorphism, which is: Given two graphs $G$ and $H$, is there a subgraph of $G$ that's isomorphic to $H$? Subgraph Isomorphism is $\mathbf{NP}$-complete.
Intuitively, it seems like these problems are "obviously" hard, but intuition has been proven wrong before. One example of this is Primality Testing: given an integer $n$, is it prime? This was proven to be in $\mathbf{NP}$ in 1975 by Pratt. But over the decades, the exact class to which Primality Testing belonged shifted, with the development of some randomized algorithms, until it was finally shown in 2004 by Agrawal, Kayal, and Saxena that Primality Testing was actually in $\mathbf P$!
All of this is to say that there is still a lot that we don't know in complexity theory and in algorithms.