tag:blogger.com,1999:blog-3722233.post5703612485495687112..comments2019-09-13T06:20:55.925-04:00Comments on Computational Complexity: FCRC 2019Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger3125tag:blogger.com,1999:blog-3722233.post-53655241271758767972019-07-29T07:05:07.992-04:002019-07-29T07:05:07.992-04:00I finally read Structurally Cyclic Petri Nets (9 p...I finally read <a href="https://arxiv.org/abs/1510.08331" rel="nofollow">Structurally Cyclic Petri Nets</a> (9 pages) by F Drewes, J Leroux – 2015. It was surprisingly easy to read, and answered many more questions (which I actually had before even starting to read the paper) than indicated by the short three sentence abstract. At the end of section 2, the authors indicate for the first time that they will also prove P-hardness of the structural cyclicity problem. So they obtain the main result of the paper as<br />Corollary 6.4. <em>The structural cyclicity problem is P-complete, regardless of whether numbers are encoded in binary or unary.</em><br />but mention it neither in the abstract, nor the introduction, nor the conclusion. Other "bonus material" is at least mentioned in the introduction, like "Theorem 3.1. The cyclicity problem is EXPSPACE complete."<br /><br />You may ask how this is related to your post. Jérôme Leroux is one of the many authors of the mentioned best paper awardee. Turns out he is also the second author of the paper above. And he is the first author of the paper providing the best published upper bound for the reachability problem. I had never heard of him before. Looks like he made major progress on the reachability problem in 2009, but <a href="https://rjlipton.wordpress.com/2009/04/08/an-expspace-lower-bound/#comment-359" rel="nofollow">his paper got rejected from FOCS</a> for being "out of scope".<br /><br />The decision might actually even be "correct", since decidable problems from <a href="https://arxiv.org/abs/1312.5686" rel="nofollow">Complexity Hierarchies Beyond Elementary</a> are not untypical for theory B, but too "unpractical" for theory A.Jakitohttps://www.blogger.com/profile/08235089048981338795noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-53978361621940669832019-06-28T09:05:13.121-04:002019-06-28T09:05:13.121-04:00Right. I updated the post.Right. I updated the post.Lance Fortnowhttps://www.blogger.com/profile/06752030912874378610noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-14653161018852978092019-06-28T05:22:31.855-04:002019-06-28T05:22:31.855-04:00Are you sure that "This problem was known to ...Are you sure that "This problem was known to be primitive recursive "? The abstract of the paper says "the currently best published upper bound is non-primitive recursive Ackermannian of Leroux and Schmitz from LICS 2019". This seems to indicate that no primitive recursive upper bound is known yet.Jakitohttps://www.blogger.com/profile/08235089048981338795noreply@blogger.com