tag:blogger.com,1999:blog-3722233.post2010994775517576408..comments2024-03-02T02:08:38.816-06:00Comments on Computational Complexity: Is MATH Ready for P=NP? Is Alexandra Fahrenthold Ready for P=NP? Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger18125tag:blogger.com,1999:blog-3722233.post-58143364980178956402021-11-05T11:53:58.834-05:002021-11-05T11:53:58.834-05:00It was given out by Boaz Barak to all students in ...It was given out by Boaz Barak to all students in CS121 (Harvard's introductory theory course). Boaz was following a tradition that dates all the way back to ... when Bill Gasarch was Harry Lewis's TF for this course! Anyway, I suppose Boaz would be the source, though I imagine the original lot is all gone. Harry Lewishttps://www.blogger.com/profile/17088418333536732728noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-88454487684888619192021-11-05T11:53:12.517-05:002021-11-05T11:53:12.517-05:00It was given out by Boaz Barak to all students in ...It was given out by Boaz Barak to all students in CS121 (Harvard's introductory theory course). Boaz was following a tradition that dates all the way back to ... when Bill Gasarch was Harry Lewis's TF for this course! Anyway, I suppose Boaz would be the source, though I imagine the original lot is all gone. Harry Lewishttps://www.blogger.com/profile/17088418333536732728noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-7074879468969274352021-10-22T09:00:50.919-05:002021-10-22T09:00:50.919-05:00In this case, Feynman was wrong. Math can help, bu...In this case, Feynman was wrong. Math can help, but it is not only a math problem. It is an applied math problem. Many people today understand Quantum Mechanics. The odd thing is that so many people resist including the equation that tells you how the particles actually move (that's what "mechanics" means). Even when Feynman said it, there were people who understood Quantum Mechanics.David Marcushttps://www.blogger.com/profile/07084520656051241766noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-17143965566727647752021-10-21T21:11:46.147-05:002021-10-21T21:11:46.147-05:00@Timothy, this opinion is quite intriguing, though...@Timothy, this opinion is quite intriguing, though, substantially boils down again to defining "too much junk" without boiling down something to triviality. <br />Why is 2-SAT in P and 3-SAT isn't? Does this include "too much junk"? How would you go about this?<br />EGnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-77531839763386929782021-10-21T13:35:36.209-05:002021-10-21T13:35:36.209-05:00Feynman said that NOBODY understands quantum mecha...Feynman said that NOBODY understands quantum mechanics. Maybe that would be a better problem- use math to help us UNDERSTAND QM.gasarchhttps://www.blogger.com/profile/03004932739846901628noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-76675956504541325892021-10-21T13:34:17.759-05:002021-10-21T13:34:17.759-05:00If P=NP this could happen: some algorithmic trick ...If P=NP this could happen: some algorithmic trick that ONCE YOU SEE IT you wonder how we all missed it.<br /><br />If P NE NP I think this is unlikely--- we have some proofs that certain techniques will not work, and generallly proving something CANNOT be done is hard. And as Timothy Chow said in an earlier comment: the notion of arbitrary computation lacks structure, making it hard.<br /><br />Of course, having said that, Alexandra will show P NE NP over the summer and I will look foolish. If I understand the proof, that would be okay with me. gasarchhttps://www.blogger.com/profile/03004932739846901628noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-3259705714088934002021-10-21T07:28:02.240-05:002021-10-21T07:28:02.240-05:00Very nice and informative post.
Important questio...Very nice and informative post. <br />Important question left open though: Where can we buy the t-shirt?Wim Martenshttps://www.blogger.com/profile/06590515701620322833noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-88100036101657318912021-10-21T05:17:20.198-05:002021-10-21T05:17:20.198-05:00What if the problem turns out unexpectedly simple?...What if the problem turns out unexpectedly simple?Anonymoushttps://www.blogger.com/profile/15215802322939426847noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-13986111052487002602021-10-20T05:36:33.346-05:002021-10-20T05:36:33.346-05:00As an "amateur" I threw a few hours on m...As an "amateur" I threw a few hours on many "tiny easy impossible" problems ... <br /><br />Now I honestly ask myself WHY they are so difficult to solve, and using Occam's razor an answer come to mind:<br /><br />* according to our "way of reasoning" the proofs are "random"<br /><br />... clearly I don't even know if such a sentence could have any meaning :-)Marzio De Biasihttps://www.blogger.com/profile/18441670787376943932noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-2641648837501096672021-10-18T17:40:27.253-05:002021-10-18T17:40:27.253-05:00One "alternative way of looking at it" t...One "alternative way of looking at it" that I could imagine happening is something like this. We (collectively) decide that P is too large a class; it contains all kinds of junk that we don't care about. We define a proper subclass P' of P that contains "everything we care about." P' contains enough structure that we are able to separate it from NP. We decide that this separation "essentially resolves" the P vs NP problem, and regard the original P vs NP problem as being the wrong question.Timothy Chowhttp://alum.mit.edu/www/tchownoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-55436800920090440272021-10-18T16:17:06.608-05:002021-10-18T16:17:06.608-05:00All: I have a next-generation bespoke computationa...All: I have a next-generation bespoke computational platform designed to ferret out patterns which can then drive the mathematics and proof. I purport to have a proof for all Collatz orbits including bounds and understand why Tao's tour De force approach would not ferret out the interplay ofmultple numeric series found in CZ and prime series. My platform also ferreted out a novel prime distribution implying twin prime conjectures are true and validated a geometric-calculus non elliptic proof of FLT explaining why FERMAT thought he had an elegant proof but hit a math wall. Any suggestions sannerwind@gmail.com Jay Rosenberg JayRhttps://www.blogger.com/profile/14504188258447135068noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-8139761358951733792021-10-18T14:14:05.761-05:002021-10-18T14:14:05.761-05:00Did you ever think about additional/imaginary info...Did you ever think about additional/imaginary information that might be given by a random tsp? Let's say we have n = 10 and let's say its in the plane. <br />Let's assume every point has a certain mass. And let's assume in this system gravity exists.<br />Then just by giving 10 random locations for the 10 dots their gravity would define a gravitational effect on the whole plane. <br />My question for this would be if it is possible theoreticly that the 10 points would not change their postion<br />because they would be pulled together by gravity. Thinking about that I came across 1 obvious solution if the dots were so far from each other that the gravitational effect would be irelevant.<br />But then it also wouldnt help with a solution. But I was then thinking that maybe its possible to calculate for these 10 dots a certain mass after their position and distance was randomly decided.<br />So that they would always stay at their position despite having a mass and causing gravitation because the effects of every dot would cancel each other.<br />Those are just ideas I am not done thinking about that. But I do think there is more information with this problem wating to be observed and used. <br />And until we have not considered every posible bit of information for the solution it would be too early to conclude its outside of p.<br /><br />The idea for this gravitational effect is simple. If you naively look at a random tsp with 10 dots and start including paths to the solution some seem more logical then others. And this gravitational effect <br />would just give more insight on some paths that seem logical but end up not being in the final solution after you checked.<br /><br />I ran a lot of different naive ideas on a random tsp with n = 7 to 9. For example I checked how often the shortest of all paths would be in the final solution. And actually it was most of the time included.<br />Something like ~495/500 times. If the gravitational (or any other additional point of view) gives insight on why in those 5 cases the shortest path was a bad idea finding the perfect solution every time appears more realistic.<br />Instead of just checking the length of the paths and including the shortest you would probably check for the easiest/cheapest path based on gravity and distance. <br />Say you would compare traveling from earth to sun to traveling to an asteroid in the opposite direction at 1 AU distance. The journey to the sun has the same distance but would be a lot faster. <br />In general to the sun is the better journey. But looking at the distance of those 3 objects its a 50-50 chance which path is better.Anonymoushttps://www.blogger.com/profile/08822834907914640458noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-63810440991966289342021-10-18T14:07:15.130-05:002021-10-18T14:07:15.130-05:00Most of the times when the shortest path is not wi...Most of the times when the shortest path is not within the real solution its obvious why thats the case. If the shortest path is connecting A and B its then ignoring some third point C in the proximity of A and B and<br />in the final solution the paths AC and CB are included.<br />But way more interesting: most of the time that the shortest path is not within the final solution is when the final solution is a complex n-gon and not a simple one. Thats the same with most other naive tests I did.<br />I would actually make the case that if the final solution is a simple n-gon it must be possible to find that solution in polynomial time.<br />It is just so much simpler if you can ignore all the complex cases. The challenge then would be to construct the n-gon with the shortest circumference.<br />If you include the complex n-gon solutions the big problem is defining the circumference of it in a useful way first of all.<br />Actually I am sure if you define it correctly any complex n-gon could be folded out to a convex polygon with the exact same surface area and circumference.<br />But so far the definition of a complex polygon has not much todo with folding. Anyway it would be hard (impossible) to tell just with the random points along which path the polygon is folded. <br />In short: If 2 paths of the solution intersect its a complex polygon but it could be converted into a simple polygon by folding it along 1 of the paths n² paths.<br />So yes I think if you wouldnt have to deal with complex n-gon solutions it would be pretty obvious to be polynomial.<br />One other insight that I got is that n does not really define the difficulty of finding a solution. <br />You could give me a tsp with a billion n if those points are aligned in circle or square or potentialy any other convex n-gon I could give you the correct solution instantly.<br />But now to the big problem. I said I am sure if the final solution to a given tsp of size n is a simple n-gon its easy to find that solution. Thats often the case for small n. <br />But I am sure the bigger n the more unlikely it becomes that the solution actually is a simple and not a complex n-gon but never impossible.<br /><br />One other thing to mention: Very often for n = 7 to 9 the simple n-gon with the shortest circumference is actually very close to the real solution. I dont see a reason why that would change with higher n.<br />So just searching the simple n-gon with the shortest circumference might be a far better approach then the minimum spanning tree heuristic.<br /><br />In the end I think its hard to say if math is ready for this problem but it feels like there is still a lot to try even with our understanding of math. But as you said in the article, who has the time?Anonymoushttps://www.blogger.com/profile/08822834907914640458noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-20186470772965559792021-10-18T13:20:46.645-05:002021-10-18T13:20:46.645-05:00AH- the key word in your post argument is ``arbitr...AH- the key word in your post argument is ``arbitrary''-- there HAVE been lower bounds on restricted models (decision trees, restricted types of circuits) but perhaps those have structure.<br /><br />Even so, maybe one day they (not sure who `they' are) will find the needed structure OR an alternative way of looking at it. The work on Greek3 makes me optimistic in the very long run- it took an entirely new mindset, but they did crack it. <br /><br />I found an online copy of the article on Wantzel- it is interesting (might be the starting point for another blog post) and here it is:<br /><br />https://www.sciencedirect.com/science/article/pii/S031508600900010X<br />gasarchhttps://www.blogger.com/profile/03004932739846901628noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-22915917258780320042021-10-18T13:10:07.404-05:002021-10-18T13:10:07.404-05:00Regarding "H6: Make Physics rigorous", i...Regarding "H6: Make Physics rigorous", it does seem a bit open ended. Going by what Wikipedia says, there does seem to be work being done in this area.<br /><br />Just making physics understandable to mathematicians might be a good goal. For example, there is "Physics for Mathematicians, Mechanics I" by Michael Spivak. (I haven't read it.)<br /><br />Regarding Quantum Mechanics, it would help if physicists stopped saying things like "cats can be both alive and dead". Sheldon Goldstein is a mathematician who has helped bring some sense to Quantum Mechanics, https://sites.math.rutgers.edu/~oldstein/.David Marcushttps://www.blogger.com/profile/07084520656051241766noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-38611437914432913852021-10-18T12:17:28.325-05:002021-10-18T12:17:28.325-05:00Regarding Wantzel, see the very interesting paper ...Regarding Wantzel, see the very interesting paper by Jesper Lützen, "Why was Wantzel overlooked for a century? The changing importance of an impossibility result" (Historia Mathematica<br />Volume 36, Issue 4, November 2009, Pages 374-394). In a nutshell, Lützen thinks that it's because at the time, impossibility results were not regarded as being that interesting.<br /><br />Tao's result on the Collatz conjecture is very impressive, but it does not bring us any closer to resolving the actual conjecture.<br /><br />In my opinion, one fundamental difficulty with P vs NP is that *arbitrary computations lack structure*. If a difficult math problem is finally solved after decades or centuries, it's almost always because people managed to find hidden structure. The pessimism about Ramsey numbers and the Collatz conjecture stems from the feeling that there isn't any hidden structure to be found. From this point of view, P vs NP is closer to Ramsey and Collatz than to Fermat or Poincare.<br /><br />For similar reasons, I am skeptical that geometric complexity theory will lead anywhere; they're essentially betting that there's some structure to be found in an arbitrary computation, and that just seems overly optimistic to me.Timothy Chowhttp://alum.mit.edu/www/tchownoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-48952392381595168202021-10-18T08:13:37.847-05:002021-10-18T08:13:37.847-05:00Fixed.
I would advise Alexandra to work on P vs NP...Fixed.<br />I would advise Alexandra to work on P vs NP or Riemann rather than R(5,5). She will learn more from the quest to solve P vs NP or Reimann than R(5,5). But I join you in wishing her luck on whatever math problem she will work on this summer!gasarchhttps://www.blogger.com/profile/03004932739846901628noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-39093412011488617292021-10-18T08:08:44.689-05:002021-10-18T08:08:44.689-05:00typo: R(5) -> R(5,5)
Good luck, Alexandra!typo: R(5) -> R(5,5)<br /><br />Good luck, Alexandra!Dave Lewishttps://www.blogger.com/profile/06172997671895163683noreply@blogger.com