P vs NP and Angle Trisection (serious question)

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.

Answer 1

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).

Answer 2

First of all, P vs NP is about computability by Turing machines/computers and not about straightedge and compass constructions.

Your "problem", as you suspect, does not really fit the definition of "problem" in the sense of P vs NP.

A problem in the sense of P vs NP (formally called a "language") is simply a set of (binary) strings. So, if $\{0,1\}^*$ denotes the set of all binary strings, then a language is simply any $L\subseteq \{0,1\}^*$. The "problem" associated with a language $L$ is simply to check, given an arbitrary binary string $x$, whether $x\in L$ or not.

As a simple example, "the set of all gramatically correct English sentences" could be a language (the sentences should be encoded as binary strings but this is just a detail). Another example would be "the set of all numbers that are composite numbers (i.e., numbers which are not prime)". Being able to solve these problems quickly means being able to quickly (i.e., polynomial time) determine whether a sentence is valid English or whether a number is composite.

Formally, a problem can be "quickly checked" if there exists a procedure/algorithm/Turing machine that takes two inputs (binary strings) $x,y$. Given $(x,y)$, the algorithm must output either "yes" or "no". The rules are as follows:

• If $x\not \in L$, then the output is always "no".

• If $x\in L$, then there is some $y$ such that the output for $(x,y)$ is "yes".

And this must be done quickly (in polynomial time in $|x|$). You can think of $y$ as a "solution" for the problem instance $x$ and the algorithm as checking whether a solution is correct.

Going back to the example of composite numbers, the string $y$ could be the prime factorization of $x$. The procedure would take $y$ and verify that the numbers in $y$ when multiplied give $x$ (and then either output "yes" or "no" accordingly). This means that the "composite number problem" is in NP.

To cast "angle trisection" as a computational problem we would first have to define an encoding of "angles" as binary strings. Supposing that could be done, we could define $L$ as the set of (binary encodings of) angles that admit a straightedge/compass trisection. Clearly $L$ would be the empty set (or just the set of representations of $0^\circ$ angles if you allow those). The problem $L$ is trivial to solve since we can just output "no" by default since no (non-trivial) angle can be trisected.