tag:blogger.com,1999:blog-3722233.post5239126614687457438..comments2020-10-29T13:56:19.634-05:00Comments on Computational Complexity: Sparse problems in NP thought to not be in PLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger10125tag:blogger.com,1999:blog-3722233.post-41867304791973600292010-07-15T16:41:50.755-05:002010-07-15T16:41:50.755-05:00To me, the people who desperately want to factor, ...To me, the people who desperately want to factor, don't come into the equation at all. They are practical people and would be satisfied by an exponential algorithm provided the runtime was still fast enough (tiny coefficient in front of a barely-bigger-than-1-base exponent) to easily crack RSA. And conversely they'd be displeased with a polynomial-time algorithm if the degree of the polynomial was 5000 digits. So there's very little real relation...Xamuelhttp://www.xamuel.com/category/math/noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-25791525864572772212010-07-15T15:14:00.150-05:002010-07-15T15:14:00.150-05:00@John: I am not totally sure but maybe the answer ...@John: I am not totally sure but maybe the answer to your question can be deduced from <br />http://www.springerlink.com/content/9273811760307743/Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-44674537841135856832010-07-15T13:31:07.399-05:002010-07-15T13:31:07.399-05:00Discrete Log sits in BQP (and in NP \intersect co-...Discrete Log sits in BQP (and in NP \intersect co-NP as explained above), so all the Factoring arguments apply to dlog as well.Wim van Damhttps://www.blogger.com/profile/14484831637730978511noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-86494462657931081902010-07-15T12:24:20.211-05:002010-07-15T12:24:20.211-05:00Forgive me if this is to far off track- but this d...Forgive me if this is to far off track- but this discussion brings to mind a problem that has disturbed me for a while. It is not quite sparse, but it feels similar in that it has very little expressive power (there for it is hard to use it as a target of a reduction). Given: a set of linear inequalities and a set of points- do they represent the same convex set? Anyone know the state of this problem? The problem has a easy co-structure (just show one of the vertices violates an inequality or exhibit a new feasible point not in the convex hull of the vertices) but I don't know of prove the affirmative method.John Mounthttp://www.win-vector.com/blog/noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-42814852250903376732010-07-15T12:17:46.009-05:002010-07-15T12:17:46.009-05:00B.--there are plenty of sparse sets provably not i...B.--there are plenty of sparse sets provably not in P. For instance, a random subset of 1^*, the all-ones strings.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-32510283656965516262010-07-15T12:15:26.091-05:002010-07-15T12:15:26.091-05:00> Discrete Log. Actually, are there reasons to ...> Discrete Log. Actually, are there reasons to think this is NOT NPC?<br /><br />What is the decision version of your DLOG problem? Let's consider this version: Given a prime p, a generator g of (Z/pZ)^* and two numbers a and b in {1,...,p-1}, is the unique i such that a = g^i mod p smaller than b? An oracle to this problem lets you find discrete logs by binary search.<br /><br />This problem is clearly in NP and is also in co-NP because if the unique such i is not smaller than b then you can guess it and verify it.<br /><br />If you are worried about the promise in the input that g is a generator of (Z/pZ)^*, please note that this promise can also be checked in NP \cap co-NP: for a certificate that g is a generator guess the factorization of p-1 and check that g^{(p-1)/q} \not= 1 mod p for every prime factor q of p-1, and for a certificate that g is not a generator guess some i < p-1 such that g^i \not= 1 mod p.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-10707558900718561722010-07-15T11:12:24.648-05:002010-07-15T11:12:24.648-05:00Hartmanis-Immerman-Sewelson (1985): There are no s...Hartmanis-Immerman-Sewelson (1985): There are no sparse sets in NP-P iff E=NE (<a href="http://dx.doi.org/10.1016/S0019-9958(85)80004-8" rel="nofollow">reference</a>)Lance Fortnowhttps://www.blogger.com/profile/06752030912874378610noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-70104105617976331322010-07-15T11:12:23.942-05:002010-07-15T11:12:23.942-05:00@Lance: whoops. Just saw your comment.@Lance: whoops. Just saw your comment.Joshnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-39618125097082198702010-07-15T11:11:51.403-05:002010-07-15T11:11:51.403-05:00How about the padded version of any natural NEXP-c...How about the padded version of any natural NEXP-complete set? But maybe padded versions of natural languages no longer count as natural?Joshnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-43229971354636921782010-07-15T10:45:32.071-05:002010-07-15T10:45:32.071-05:00Let me ask a silly question: Mahaney Theorem says ...Let me ask a silly question: Mahaney Theorem says "if a sparse set is NP-complete, then P=NP". Is there anything known about "if a sparse set is not in P, then ???" ?B.noreply@blogger.com