P vs NP and Angle Trisection (serious question) I have a question. Please be nice; I come from the corporate world and my knowledge of computer theory is around a college freshman level.

My understanding from many popular-level sources (like Scott Aaronson's P vs NP for dummies blog post, or this New Yorker article) is that the P vs NP question asks whether a problem that can be checked "quickly” can also be solved "quickly". But to my knowledge there are well-known problems that can be checked quickly but are impossible to solve regardless of time or number of operations.

Take, for example, the (in)famous angle trisection with straightedge and compass. If asked to check that a provided angle really does trisect 60 degrees, you can very quickly verify that fact using a straightedge and compass. But if someone asks you to solve the problem of trisecting that 60 degree angle using the same straightedge and compass, you can’t do it. So the solution here really only goes "one way" (i.e. using classical tools, the 20 degree angle can be checked really quickly, but no finite amount of operations/time will ever solve the problem of constructing it). 

How does this relate to P vs NP? My thought is that this would show that NOT every problem that can be checked quickly can be solved quickly. The specific case of the 60 degree angle trisection appears to be checked in P time and not solved in P time (or any time for that matter, because by using classical tools the problem of the 60 degree trisection cannot be solved at all).

I know I’m missing something, and I tried looking up the formal definition of P vs NP on the Clay Math website, and that was way over my level of understanding (I’m betting that the categories of P and NP don’t apply to my example for reasons I am just not aware of). I just went through the exercise and tried to intuit the question using some well-known math, and I’m having a tough time figuring out where my mistake is. 

Any thoughtful feedback is very much appreciated :)

PS: This was moved from CS Theory StackExchange b/c it is not a research q.
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).