A language $B$ is $\mathbf{NP}$-hard if $A \leq_P B$ for all $A \in \mathbf{NP}$. A language $B$ is $\mathbf{NP}$-complete if $B \in \mathbf{NP}$ and $B$ is $\mathbf{NP}$-hard.
These definitions turn out to be extendible to other complexity classes in general. For a complexity class $\mathcal C$, we say that a language $B$ is $\mathcal C$-hard if $A \leq_P B$ for all $A \in \mathcal C$ and $B$ is $\mathcal C$-complete if $B \in \mathcal C$ and $B$ is $\mathcal C$-complete.
The idea behind hardness is that those problems that are $\mathcal C$-hard are supposed to be the "hardest" problems of the class. So if you're able to solve one of them, you should be able to solve any other problem in $\mathcal C$. Of course, just because a problem is $\mathcal C$-hard doesn't mean that the problem has to be in $\mathcal C$, which is why there is the additional requirement for completeness. Such complete problems are supposed to be the hardest problems that are also members of their class.
This leads us to the following results.
Theorem. If $B$ is $\mathbf{NP}$-complete and $B \in \mathbf P$, then $\mathbf P = \mathbf{NP}$.
Theorem. If $B$ is $\mathbf{NP}$-complete and $B \leq_P C$ for $C \in \mathbf{NP}$, then $C$ is $\mathbf{NP}$-complete.
Proof. We already know $C$ is in $\mathbf{NP}$. Since $B$ is NP-complete, every language in $\mathbf{NP}$ is polynomial time reducible to $B$. Note that polynomial time reductions compose. Then since $B \leq_P C$, this implies that every language in $\mathbf{NP}$ is polynomial time reducible to $C$. $$\tag*{$\Box$}$$
The implications of the above two results are quite significant. Basically, if we want to show that $\mathbf P = \mathbf{NP}$, then all we need to do is show that just one problem that is $\mathbf{NP}$-complete reduces to problem in $\mathbf P$, or equivalently, has a polynomial time algorithm.
Of course, it's not entirely obvious that $\mathbf{NP}$-complete problems even exist. And if they do, there are a whole bunch of questions we can ask about such problems. For instance, it's not obvious that an $\mathbf{NP}$-complete problem is necessarily something useful or natural that someone would want solved. Or, how many such problems are there? It could be that there are only a few esoteric $\mathbf{NP}$-complete problems, kind of like those weird results we saw from the early days of complexity theory.
These questions have obviously been resolved at this point and we're familiar with the discovery and implications. Stephen Cook showed what was essentially the first $\mathbf{NP}$-complete problem while defining the notions of $\mathbf{NP}$-completeness. What's sometimes not reflect upon in this discussion is the fact that this problem is a real problem and not some artificial toy problem. After all, it's quite daunting to show that every problem in $\mathbf{NP}$ can somehow reduce to this first problem.
But once we're able to get this one problem, then we can just show that other problems are $\mathbf{NP}$-complete by reducing from this first one. But again, it's not clear that many interesting problems are necessarily $\mathbf{NP}$-complete. And so Richard Karp's 1972 paper gave us a bunch of different problems across many different fields that were, while demonstrating how powerful $\mathbf{NP}$-completeness can be.
In 1979, Garey and Johnson published a book which contained approximately 300 problems that were shown to be $\mathbf{NP}$-complete. Today, we don't really have an accurate count anymore, but the number of problems ranges in the thousands and tens of thousands. And as we get more examples of $\mathbf{NP}$-complete problems, we can reduce from any of the problems we already know are $\mathbf{NP}$-complete.
Showing any one of these problems has a polynomial time algorithm is enough to show that $\mathbf P = \mathbf{NP}$.
The first problem which was shown to be $\mathbf{NP}$-complete is called the satisfiability problem, or $\mathrm{SAT}$. This was shown by Stephen Cook in 1971 and independently by Leonard Levin in 1973. This is a problem from propositional logic.
Recall that a boolean variable can take on a value of True or False. A boolean formula is an expression involving boolean variables and the boolean operations AND, OR, and NOT. A boolean formula is satisfiable if some assignment of 0s and 1s to to the variables makes the formula evaluate to True.
$\mathrm{SAT}$ asks, given a boolean formula, whether or not it is satisfiable.
Theorem. (Cook-Levin) $\mathrm{SAT}$ is $\mathbf{NP}$-complete.
Now we'll finally get around to proving that $\text{SAT}$ is $\mathbf{NP}$-complete. It would be silly if after all of the reductions we've done that SAT wasn't NP-complete, since we've sort of hinged everything on that. Before we get started, let's review what our objective is. We need to show that SAT is NP-complete. In other words, we need to show that we can reduce every single problem in NP to SAT. Essentially, what we will show is that we can encode the computation of an arbitrary polynomial time nondeterministic Turing machine as a boolean formula of polynomial size.
Theorem. $\text{SAT}$ is $\mathbf{NP}$-complete.
Proof. It is clear that $\text{SAT}$ is in $\mathbf{NP}$, so we just show that $\text{SAT}$ is $\mathbf{NP}$-hard.
Let $L$ be a language in $\mathbf{NP}$ and let $M$ be the polynomial time nondeterministic Turing machine that decides it. We show that $L$ is polynomial time reducible to $\mathrm{SAT}$ by describing a way to tranform in polynomial time every input $x \in \Sigma^*$ into a boolean formula $\varphi_x$ such that $x \in L$ if and only if $\varphi_x$ is satisfiable.
We suppose that $M$ runs in time $n^k$. Then we can represent the computation of $M$ on an input word $x$ as an $n^k \times n^k$ grid called a tableau. Each row is a configuration, with the first and last columns bordered by $\#$. The first row is the start configuration of $M$ on $x$. A tableau is accepting if some row is an accepting configuration. An accepting tableau then corresponds to an accepting branch of a computation of $M$ on $w$.
Now we describe our polynomial time transformation. We let $C = Q \cup \Gamma \cup \{\#\}$ be our alphabet and define $cell[i,j]$ to be the contents of the $i,j$th cell of the tableau. Then we define a variable $x_{i,j,s}$ for every $1 \leq i,j \leq k$ and $s \in C$ by $$x_{i,j,s} = 1 \iff cell[i,j] = s.$$ Based on these variables, we construct our formula, which has four parts, $$\varphi_x = \varphi_{cell} \wedge \varphi_{start} \wedge \varphi_{move} \wedge \varphi_{accept}.$$
The first part, $\varphi_{cell}$, checks that each cell of the tableau contains exactly one symbol, $$\varphi_{cell} = \bigwedge_{1 \leq i,j \leq n^k} \left[ \left( \bigvee_{s \in C} x_{i,j,s} \right) \wedge \left( \bigwedge_{s,t \in C \\ s \neq t} \left(\overline{x_{i,j,s}} \vee \overline{x_{i,j,t}} \right) \right)\right].$$
The formula $\varphi_{start}$ encodes the start configuration. If our starting configuration is $$\# q_0 a_1 a_2 \cdots a_n \Box \cdots \Box \#$$ where $q_0$ is the initial state and the input word is $x = a_1 a_2 \cdots a_n$, then we have $$\varphi_{start} = x_{1,1,\#} \wedge x_{1,2,q_0} \wedge x_{1,3,a_1} \wedge x_{1,4,a_2} \wedge \cdots \wedge x_{1,n+2,a_n} \wedge x_{1,n+3,\Box} \wedge \cdots \wedge x_{1,n^k-1,\Box} \wedge x_{1,n^k,\#}.$$
The formula $\varphi_{accept}$ encodes the condition for an accepting configuration. In practice, this just checks that some configuration contains the accepting state $q_A$ at some point in the tableau, $$ \varphi_{accept} = \bigvee_{1 \leq i,j \leq n^k} x_{i,j,q_A}.$$
Finally, $\varphi_{move}$ encodes the legal transitions from one configuration to the next. This sounds like a lot of work, but in reality, we only have to check a small portion of each configuration. Specifically, we have to check every $2 \times 3$ block of cells to ensure that all of the transitions are valid. Why? On any transition, we have the same sequence of actions:
Rather than formally define what constitutes a legal window (since it's tedious and not super important to get the gist of the proof), we'll look at some examples.
Here, we have a transition moving left from $q_1$ to $q_2$.
| $a$ | $q_1$ | $b$ |
| $q_1$ | $a$ | $c$ |
Here, we have a transition moving right from $q_1$ to $q_2$.
| $a$ | $q_1$ | $b$ |
| $a$ | $a$ | $q_2$ |
Here, we have a transition moving to the right, out of the window.
| $a$ | $a$ | $q_1$ |
| $a$ | $a$ | $b$ |
Here, the transition is not taking place on this part of the tape.
| $\#$ | $a$ | $b$ |
| $\#$ | $a$ | $b$ |
Here, we have a transition moving on to the window from the right.
| $a$ | $b$ | $a$ |
| $a$ | $b$ | $q_2$ |
Here, we have a transition where the tape head indicator is just outside the window to the left.
| $a$ | $a$ | $a$ |
| $c$ | $a$ | $a$ |
From this, we can see that if the top row of the tableau is the start configuration and every window in the tableau is legal, then each row of the tableau is a configuration that follows from the preceding one.
Then, we can express the formula for $\varphi_{move}$, $$\varphi_{move} = \bigwedge_{1 \leq i,j \leq n^k} \text{(the $(i,j)$ window is legal)}.$$ We define the $(i,j)$ window as the window anchored at $(i,j)$ in the following way with the symbol $a_1$ in cell $(i,j)$:
| $a_1$ | $a_2$ | $a_3$ |
| $a_4$ | $a_5$ | $a_6$ |
Then we can express the expression $\text{(the $(i,j)$ window is legal)}$ by the following formula $$\bigvee_{\text{$a_1,\dots,a_6$ is a legal window}} (x_{i,j,a_1} \wedge x_{i,j+1,a_2} \wedge x_{i,j+2,a_3} \wedge x_{i+1,j,a_4} \wedge x_{i+1,j+1,a_5} \wedge x_{i+1,j+2,a_6}).$$
To see that this reduction is polynomial, we consider the size of $\varphi$. We note that the size of $\varphi$ varies based only on the size of the tableau and not the elements of the machine, such as the number of states or alphabet symbols, since those are all fixed and do not depend on the size of the input. The tablueau has $n^k \times n^k$ cells. This gives us $O(n^{2k})$ variables. Each cell has a fixed subformula in $\varphi_{cell}$, giving us $O(n^{2k})$ clauses. The formula $\varphi_{start}$ contains a subformula for each cell of the first row and thus is of size $O(n^k)$. The formulas $\varphi_{accept}$ and $\varphi_{move}$ contain fixed subformulas for each cell of the tableau, which means they of size $O(n^{2k})$. In total, $\varphi$ has size $O(n^{2k})$ and therefore is polynomial in $n$. $$\tag*{$\Box$}$$
Despite a proof of $\mathbf P$ vs $\mathbf{NP}$ being outside of our grasp, we have a fairly good idea of the structure of both classes, the problems in each class, and a lot of the implications of what happens if the problem is decided one way or another. In some sense, it is still pretty incredible that despite all that we know, it's still not enough for us to close the gap.
For instance, there are obviously lots of problems in $\mathbf P$ and we know there are tons and tons of problems that are $\mathbf{NP}$-complete. But are there any interesting problems that are in $\mathbf{NP}$ but not $\mathbf{NP}$-complete? This turns out to be a strangely fascinating question because the vast majority of problems that we know are in $\mathbf{NP}$ are also $\mathbf{NP}$-complete.
Now, if $\mathbf P = \mathbf{NP}$, then the answer is pretty clear. However, it's not obvious that it should be the case otherwise and it's a theorem of Ladner that says that there have to be intermediate problems if $\mathbf P \neq \mathbf{NP}$.
Theorem. (Ladner) Suppose that $\mathbf P \neq \mathbf{NP}$. Then there exists a language $L \in \mathbf{NP} \setminus \mathbf P$ that is not $\mathbf{NP}$-complete.
Again, the sheer number of $\mathbf{NP}$-complete problems makes the question of the existence of such problems interesting. If we really believe that $\mathbf P \neq \mathbf{NP}$, then there must be some $\mathbf{NP}$-intermediate problems. But with almost every known problem in $\mathbf{NP}$ being $\mathbf{NP}$-complete, it's a bit strange that we have very few natural intermediate problems.
Even for the problems that are candidates, we're still not completely sure; we do not have a polynomial time algorithm but we also do not believe they are $\mathbf{NP}$-complete. Two of these problems are factoring and graph isomorphism. Factoring is quite interesting because it's often erroneously used as an example of a problem that's $\mathbf{NP}$-complete, but we actually don't know this. Furthermore, factoring is one of those problems for which quantum computation provides a polynomial time algorithm, which is something that doesn't hold for $\mathbf{NP}$-complete problems in general.