tag:blogger.com,1999:blog-3722233.post1680472021350980055..comments2024-10-10T06:29:39.038-05:00Comments on Computational Complexity: A Primer on Graph IsomorphismLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger5125tag:blogger.com,1999:blog-3722233.post-25325491541663104682015-12-09T01:43:05.404-06:002015-12-09T01:43:05.404-06:00If GI turns out to be NP complete does that mean w...If GI turns out to be NP complete does that mean we will be living in heuristica in Impagliazzoâ€™s five worlds? What I mean by this is there are already good heuristics which work very well and finding an hard instance is tough. So if $3SAT$ reduces to $GI$ then most cases of $3SAT$ are easy except a few rare instances?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-16324801549838227402015-11-12T20:37:17.128-06:002015-11-12T20:37:17.128-06:00FYI. The talk was later moved to Kent hall. FYI. The talk was later moved to Kent hall. Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-49674570183536085952015-11-12T14:50:15.025-06:002015-11-12T14:50:15.025-06:00Lance is right. It is called APR algorithm.
https:...Lance is right. It is called APR algorithm.<br />https://en.wikipedia.org/wiki/Adleman%E2%80%93Pomerance%E2%80%93Rumely_primality_testAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-46712875046164492572015-11-12T12:05:17.537-06:002015-11-12T12:05:17.537-06:00A 1981 survey by Pomerance states that Adleman and...A 1981 <a href="http://dx.doi.org/10.1007/BF03022861" rel="nofollow">survey</a> by Pomerance states that Adleman and Rumely had a n^O(log log n) time algorithm for primality. Lance Fortnowhttps://www.blogger.com/profile/06752030912874378610noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-8210527051661480752015-11-12T11:14:21.721-06:002015-11-12T11:14:21.721-06:00Lance, was Primality testing known to be in quasi-...Lance, was Primality testing known to be in quasi-polynomial time (before AKS)? It was in RP \cap co-RP but AFAIK the best known deterministic algorithm was still exponential. Is that not accurate?D. Sivakumarhttps://www.blogger.com/profile/05750992965116762335noreply@blogger.com