2
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ Check our reference question. $\endgroup$ – Yuval Filmus May 3 '20 at 10:03
  • 3
    $\begingroup$ You got useful feedback on CSTheory, but you don't appear to have updated the question based on that feedback -- it looks like you just copy-pasted the same question here. That is not very helpful. If you would like good answers, it would be better to use the feedback you received to improve your question. $\endgroup$ – D.W. May 3 '20 at 15:51
  • 2
    $\begingroup$ Some people have investigated cryptography in a world where usual notions of efficient computation are replaced by compass and straightedge constructions. It's pretty interesting and closely related to your question: en.wikipedia.org/wiki/Geometric_cryptography $\endgroup$ – Lorenzo Najt May 3 '20 at 17:59
  • 1
    $\begingroup$ Trisection of all angles is not possible using straightedge & compass. The issue has nothing to do with P vs NP. PS What is your question? What does "How does this relate to P vs NP?" mean? This is too vague. The 2 statements, or variants of them, are simply 2 statements & you are asking for some ill-defined precis about them. Find out what each is & ask some specific answerable question. $\endgroup$ – philipxy May 3 '20 at 19:21
  • 1
    $\begingroup$ Your intuition at least suggests why most (but by no means all) researchers in the field suspect that P != NP but that we lack the tools to prove this. To stretch your analogy a little, geometers suspected that trisecting an arbitrary angle was impossible, but for millennia lacked the tools to prove it. $\endgroup$ – John Coleman May 3 '20 at 19:34
3
$\begingroup$

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

$\endgroup$
11
  • $\begingroup$ Thanks for putting in the effort, I really like the answer. May I ask some clarifying questions? i)"it is not clear how to check whether the point 𝑐 can be constructed". I especially created my example so that according to the rules it cannot be constructed (point 𝑐 in this context being sin(20) or something like that) ii) "it is not completely clear how to specify the input, and what operations are allowed on it". My understanding is that straightedge and compass constructions are also formally defined, and there are lots of math proofs associated with these constructions. $\endgroup$ – ActuarialNinja May 3 '20 at 10:53
  • $\begingroup$ ii) We usually assume that the input is given in textual form. This doesn't work for real inputs. However, there are models (like the so-called Real RAM) which support real inputs, and also specify what kinds of operations are allowed on them. The set of allowed operations is important here, just as some numbers are constructible using straightedge and compass, and others are constructible using a trisector. The set of operations here define what an algorithm solving the problem is allowed to do. $\endgroup$ – Yuval Filmus May 3 '20 at 10:58
  • 1
    $\begingroup$ I think I am slowly getting what you are saying. Rephrasing in my own words (ie "for dummies"), computers can only deal with discrete units of information, whereas my example deals in Platonic mathematical abstractions like idealised lines and circles and their intersection. Therefore my problem isn't something that a computer can do at all (because a computer can't deal with "actual" circles, only discrete approximations of circles to some desired accuracy). That's my layman take on what's said here. To really show that P!=NP, I would have to show some "one way" function for discrete... $\endgroup$ – ActuarialNinja May 3 '20 at 11:11
  • 1
    $\begingroup$ ... objects like the 3-coloring of a graph or the solution to a Sudoku or something like that. Well, at least that's my best try at understanding why my example breaks down. (PS, you answered before I could even finish the thread. Your homepage says you were fast, and that was no joke, lol) $\endgroup$ – ActuarialNinja May 3 '20 at 11:13
  • 1
    $\begingroup$ By the way, for real computation we have the following: "Given a multivariate polynomial of degree 4 with at least one real zero, determine whether it has a real zero with all coordinates non-negative". The P vs NP question asks whether this question can be solved using polynomially many arithmetic instructions (including comparisons), where "polynomially" is with respect to the number of variables of the polynomial. You can check this survey if you're interested. $\endgroup$ – Yuval Filmus May 3 '20 at 11:18
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.