P vs NP and Angle Trisection (serious question)
Here is a possible analog of the P vs NP question for straightedge-and-compass constructions.

Suppose that we are given a line with three points $a,b,c$ on it, and consider the following question:


  Given just the line and the points $a,b$, can we construct the point $c$ using a straightedge and compass?


If we are given a construction, then we can verify that it indeed constructs the point $c$. But without such a construction, it is not clear how to check whether the point $c$ can be constructed.

However, this connection is a bit misleading, for various reasons, among which is that it is not completely clear how to specify the input, and what operations are allowed on it; in contrast, the P vs NP question is completely formal.



The P vs NP question is a scaled-down version of other questions in computability theory, whose answer is known. For example:


  Given a C program $P$, does $P$ ever halt?


If $P$ halts, then we can verify it by running $P$ and checking that it eventually halts; you can think of this as a verification process in which the witness is the execution trace of $P$. But without an execution trace, it is not so clear how to determine whether $P$ ever halts. Indeed, Turing proved that no algorithm can determine whether a given C program ever halts.



The $\mathsf{P}\stackrel?=\mathsf{NP}$ question can be stated as follows:


  Is there a polynomial time algorithm to determine whether an input graph is 3-colorable?


(A graph is 3-colorable if we can color its vertices using 3 colors so that the endpoints of each edge get different colors.)

Given a 3-coloring, it is easy to check (in polynomial time) that it is a valid 3-coloring. But without such a 3-coloring, it is not clear how to check whether a given graph is 3-colorable. Indeed, people conjecture that this cannot be done in polynomial time (but it can obviously be done in exponential time, by trying all possible 3-colorings).