##### Department of Mathematics,

University of California San Diego

****************************

### Zoom for Thought

## Nicholas Karris

#### UCSD

## Cliques, Covers, Cycles, and Salesmen: Reducing Hard Problems to Harder Ones

##### Abstract:

The traveling salesman problem is one of the best-known examples of an algorithmically hard problem, but what does that mean formally? It turns out that a solution to this problem would immediately give a solution to any other NP problem, and in this sense we say it is "NP-complete." In this talk, we will give a more formal definition of what it means for a problem to be NP-complete, develop the machinery needed to prove NP-completeness, and then use this machinery to prove that the traveling salesman problem (and a few others) is indeed NP-complete.

### January 5, 2022

### 2:00 PM

Please see email with subject "Grad Student Seminar Information."

****************************