Timeline for Analogues of P vs. NP in the history of mathematics
Current License: CC BY-SA 4.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 9, 2023 at 16:50 | comment | added | François Jurain | @JohnStillwell Consider the class of all planar domains whose boundary can be drawn with ruler and compass, from 2 given points one unit of length apart: I think the class qualifies as huge. Let $c$ be the side of the square with the same area as the given domain: then either $c$ can be constructed with ruler and compass or it cannot. It can, if the boundary is only drawn with line segments; the 2500+yr-problem is, what if it also consists of circular arcs. Would you say this example is in line with the original question? I think it is essentially vzn's answer. | |
| Feb 7, 2020 at 7:31 | history | edited | bof | CC BY-SA 4.0 |
added 1 character in body
|
| Mar 16, 2014 at 14:45 | comment | added | vzn | further brainstorming. this answer can be regarded as a template for using hard math problem [x] as the analogy to P vs NP. three others that are close & could be written up similarly also: unsolvability of the quintic with algebraic operations & FLT. yet another, hilberts 10th problem. all have key boundaries. | |
| Mar 16, 2014 at 3:17 | comment | added | Yemon Choi | Any chance of capitalizing sentences? | |
| Mar 16, 2014 at 3:08 | comment | added | John Stillwell | It is true that most of the work on this problem until, say, Descartes was geometric. Cantor's breakthrough was to think in terms of sets; specifically, countable versus uncountable sets. Lindemann was unaffected by this because he was proving a specific number transcendental (which is harder). If there is a message for P vs. NP it would to prove P is "small" in some sense compared with NP, rather than to find a specific NP problem not in P. Unfortunately, all attempts to transfer the concept of "small" from set theory to computational complexity theory have failed so far. | |
| Mar 16, 2014 at 2:00 | comment | added | vzn | agreed/thx for that clarification. however note that a lot of the work on the problem was geometric incl probably even some serious/reputable work and it was more later distinctions that made the picture clear about algebraic vs real numbers, ie 2020 hindsight and "modern vision/understanding/defns" superimposed on older theory. eg wonder if Lindemann used that concept at all in his proof? extending this analogy maybe P vs NP could be the tip of some new conceptual/theoretical iceberg; many TCS experts would not rule out that pov. | |
| Mar 16, 2014 at 1:39 | comment | added | John Stillwell | To bring this answer more into line with the original question, it might be better to compare the classes: algebraic numbers versus all real numbers. The existence of nonalgebraic numbers was conjectured long ago (James Gregory tried to prove $\pi$ transcendental around 1670), proved with some difficulty by Liouville in 1844, then shown to be almost trivial by Cantor 1874. | |
| Mar 16, 2014 at 1:27 | history | edited | vzn | CC BY-SA 3.0 |
added 56 characters in body
|
| S Mar 16, 2014 at 1:22 | history | answered | vzn | CC BY-SA 3.0 | |
| S Mar 16, 2014 at 1:22 | history | made wiki | Post Made Community Wiki by vzn |