tag:blogger.com,1999:blog-3722233.post7501643626120846375..comments2022-08-09T23:53:51.029-05:00Comments on Computational Complexity: Do any NP-reductions use deep mathematics? Non-rheticallyLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger17125tag:blogger.com,1999:blog-3722233.post-84572696234454840352021-04-05T18:22:43.787-05:002021-04-05T18:22:43.787-05:00I had in mind the gap/promise problem. I see now ...I had in mind the gap/promise problem. I see now the distinction you are trying to draw.Timothy Chowhttp://alum.mit.edu/www/tchownoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-33135812090500409452021-04-05T15:58:16.806-05:002021-04-05T15:58:16.806-05:00A good amount of number theory is used in the NP-c...A good amount of number theory is used in the NP-completeness proof of Diophantine binary quadratic equations:<br /><br />ax^2 + by - c = 0<br /><br />(Manders and Adleman, 1977)Marzio De Biasihttps://www.blogger.com/profile/18441670787376943932noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-89368135221605297562021-04-05T15:44:34.117-05:002021-04-05T15:44:34.117-05:00YES the 3-manifold problem definitly qualifies.
...YES the 3-manifold problem definitly qualifies. <br /><br />You may know something I do not and would be curious to know.<br />Here is what I know (and everyone does)<br /><br />CLIQ = {(G,k) : G has a clique of size k} is an NPC set<br />proof is NOT deep math<br /><br />FCLIQ(G) = return the size of the max cliq<br />FLIQ in FP iff CLIQ in P hence we do not think FLIQ is in P. <br />(Same for returning an actual clique)<br /><br />You say that from the PCP results saying FCLIQ is hard to <br />approximate you can extract a DECISION PROBLEM that is NP-complete.<br />If you mean a GAP problem (given a graph G that you are PROMISED<br />has a large or small clique, det which one) then yes.<br />If you mean an actual decision problem then I do not know that and<br />would be enlightened if you post on it- or if its too long or something then email me.<br />gasarchhttps://www.blogger.com/profile/03004932739846901628noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-44772042951735033072021-04-05T15:21:36.705-05:002021-04-05T15:21:36.705-05:00I imagine that the proof that MCSP is NP-hard uses...I imagine that the proof that MCSP is NP-hard uses "deep math".Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-11428276956660483352021-04-05T13:35:23.036-05:002021-04-05T13:35:23.036-05:00I still don't understand your attempted distin...I still don't understand your attempted distinction between APPROXIMATE and SET. By "SET" you just mean a decision problem, right? But as you know, there is a standard way to extract an NP-complete decision problem from one of the PCP-type NP-hard approximation problems.<br /><br />In any case, the 3-manifold knot genus problem mentioned by Hermann Gruber would seem to qualify according to your most recent definition, for the (trivial?) reason that it would take too much time in the course to even explain what the SET is in the first place.Timothy Chowhttp://alum.mit.edu/www/tchownoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-36353208733215903532021-04-05T12:22:20.920-05:002021-04-05T12:22:20.920-05:00"Deepness" is subjective. Suppose by &qu..."Deepness" is subjective. Suppose by "deep math" you mean that a student in a graduate level algorithms course will have trouble understanding it (which seems to be the case in your comment above). Then this is just poor classification due to exposure to different areas.<br /><br />If your problem is easy to describe typically the reductions "look" easy just because they can be understood by many people, even if they take a lot of ingenuity to come up with.<br /><br />If your problem requires several graduate math courses' worth of background to even describe then of course the reduction "looks" difficult �� even if the reduction ends up being trivial and straightforward.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-30091464641231995862021-04-05T12:13:01.533-05:002021-04-05T12:13:01.533-05:00While not likely to be NP-complete, Tensor Isomorp...While not likely to be NP-complete, Tensor Isomorphism-complete problems definitely use a lot of deep math. https://arxiv.org/abs/1907.00309Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-24197247951915482122021-04-05T12:08:39.753-05:002021-04-05T12:08:39.753-05:00AH, the 3-manifold ... problem certainly uses deep...AH, the 3-manifold ... problem certainly uses deep math by any definition. <br /><br />I wonder how common such problems are- perhaps more common in Comp Top or Comp Geom then in other parts of CS. gasarchhttps://www.blogger.com/profile/03004932739846901628noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-84557698206690598212021-04-05T12:07:02.855-05:002021-04-05T12:07:02.855-05:00The PCP stuff shows problems are hard to APPROXIMA...The PCP stuff shows problems are hard to APPROXIMATE. <br />By `reductions' I meant proofs that SETS are NP-hard.<br />So do any of those use `deep math'<br /><br />What is `deep math'? A good question which many of the comments have also commented on and helped me realize more what I was trying to ask. I will now phrase several better-defined questions<br /><br />a) Are there any proofs that a SET is NPC that uses math that a good<br />Senior CS major (who is not also a math major) has not seen and would <br />take to much time in a course to explain.<br /><br />b) Replace `good senior CS major (who is not a math major)<br />with<br />good senior CS major who IS a math major<br />1st year grad student in CS (who was/was not also a math major)gasarchhttps://www.blogger.com/profile/03004932739846901628noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-91683632824502024532021-04-05T11:54:47.081-05:002021-04-05T11:54:47.081-05:00I think you need to say a little more about what y...I think you need to say a little more about what you mean by "deep." Does it just mean "unfamiliar"? Or "from an area of mathematics with a glamorous reputation"? If we are trying to make an educated guess about whether a conjecture is true or false, then personal familiarity and glamor presumably are not very relevant concepts.<br /><br />Another thing I don't understand is why you haven't answered your own question; if PCP uses deep math then the proof of NP-hardness of certain inapproximability results must use deep math, right?<br /><br />The following MathOverflow question contains some interesting opinions about the word "deep":<br /><br />https://mathoverflow.net/q/139607/Timothy Chowhttp://alum.mit.edu/www/tchownoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-23293696629152294412021-04-05T10:31:12.583-05:002021-04-05T10:31:12.583-05:00From the commments it seems that concrete models a...From the commments it seems that concrete models and PCP DO use some deep math.<br /><br />How about my original question- do any NP reductions use deep math?gasarchhttps://www.blogger.com/profile/03004932739846901628noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-32223065485594092562021-04-05T10:16:31.527-05:002021-04-05T10:16:31.527-05:00The definition of AI problems are AI problems that...The definition of AI problems are AI problems that haven't been worked out yet. Then they are just algorithms.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-75784905199383734042021-04-05T10:10:29.192-05:002021-04-05T10:10:29.192-05:00I was not dismissing. I was more asking IF it used...I was not dismissing. I was more asking IF it used deep math. If it doe not that would NOT take away from how awesome it was- I did say that. gasarchhttps://www.blogger.com/profile/03004932739846901628noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-35009508880139795862021-04-05T09:29:02.334-05:002021-04-05T09:29:02.334-05:00Are there deep math reductions in Arithmetic versi...Are there deep math reductions in Arithmetic versions of the P/NP classes? I'd bet they would need deeper facts about varieties and what not.<br /><br />What about Mulmuley's work? Seems to require some deep math.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-86088908037657445622021-04-05T06:58:22.197-05:002021-04-05T06:58:22.197-05:00Possibly problems from computational topology or c...Possibly problems from computational topology or computational geometry qualify? I cannot judge the mathematical depth of the following result (my knowledge about 3-manifolds is very limited), but the little I understand impresses me: "3-manifold knot genus is NP-complete" by Agol, Hass and Thurston https://doi.org/10.1145/509907.510016Hermann Gruberhttp://www.hermann-gruber.comnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-50186084087690396782021-04-05T06:27:33.481-05:002021-04-05T06:27:33.481-05:00Fourier theory was introduced to CS with Håstad...Fourier theory was introduced to CS with Håstad's optimal inapproximability results. Today it might not be considered deep, but I recall when it still was.<br /><br />Also there are Algebraic Geometry codes which use downright arcane mathematics...Eldarnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-24104344515126761612021-04-05T02:40:23.871-05:002021-04-05T02:40:23.871-05:00Laci’s proof that graph isomorphism is polylog rel...Laci’s proof that graph isomorphism is polylog relies on the classification of finite simple groups. You almost certainly don’t need the whole classification, but my understanding is that you need the parts that cover the groups in question.<br /><br />I think your dismissal of the PCP Theorem is overly hasty. Significant creativity and original thought went into going from the Schwartz-Zippel Lemma to verifying computations using the sum-check protocol. If you want to classify that as “not deep” that’s one thing, but the deepest part of the (original) PCP theorem is the invention of the VC paradigm in the 90s.Stella Bidermanhttps://www.blogger.com/profile/05545219890671667382noreply@blogger.com