Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?

No polynomial algorithm exists to solve this problem. If someone could find one, it would solve one of the most important open problems in Computer Science. The consequences would be huge.

Does P equal NP?

A problem $A$ reduces to $B$ ($A\le B$) if there is a polytime algorithm converting $A$ inputs to equivalent $B$ inputs.

A problem $X$ is NP-hard if every NP problem reduces to $X$

A problem $X$ is NP-complete if it's NP and NP-hard.

Given a boolean formula such as

can you find values of $x_1,\dots ,x_k\subset \{\text{true},\text{false}\}$ for which the expression is true.

The 3SAT problem is NP-hard.

Given a Super Mario Brothers level, is it solvable?

The Super Mario Brothers problem is NP-hard.

Given an undirected graph, is there an independent set of size $\ge m$?

The IS problem is NP-hard.