tag:blogger.com,1999:blog-3722233.post1455510985147072060..comments2024-03-02T02:08:38.816-06:00Comments on Computational Complexity: Finding Primes PseudodeterministicallyLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger6125tag:blogger.com,1999:blog-3722233.post-10446748000020291662023-05-28T09:31:21.507-05:002023-05-28T09:31:21.507-05:00That takes sqrt(n) time. Remember though that when...That takes sqrt(n) time. Remember though that when we talk about the complexity of computing primes or factoring, the length of the input is the length of the number written in binary, in this case log n. So this algorithm is exponential in its length.Lance Fortnowhttps://www.blogger.com/profile/06752030912874378610noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1578479796619381532023-05-27T18:39:37.707-05:002023-05-27T18:39:37.707-05:00What is the runtime of
if (n<2) return false;
...What is the runtime of<br /><br />if (n<2) return false;<br /><br />stop = sqrt(n);<br /><br />for i = 2 to stop if (n%i == 0) return false;<br /><br />return true;<br />Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-20714844667312945182023-05-27T16:07:56.573-05:002023-05-27T16:07:56.573-05:00In this context 1^n is the string of n one's. ...In this context 1^n is the string of n one's. It's a way to use n as an input and have B run in time polynomial in n.Lance Fortnowhttps://www.blogger.com/profile/06752030912874378610noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-85317939100460588912023-05-27T15:33:40.589-05:002023-05-27T15:33:40.589-05:001^n is always 11^n is always 1Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-63631118365847882262023-05-25T08:59:24.667-05:002023-05-25T08:59:24.667-05:00Good point. I made it trivial as written. The pape...Good point. I made it trivial as written. The paper really says for infinitely many n, B(1^n) will output a prime of length n. I'll fix the post.Lance Fortnowhttps://www.blogger.com/profile/06752030912874378610noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-45722803637249668862023-05-25T08:56:30.109-05:002023-05-25T08:56:30.109-05:00It seems that if the algorithm just outputs B(m) =...It seems that if the algorithm just outputs B(m) = m always, this should also work infinitely often (namely, when m is a prime.) The algorithm can also check if m is a prime in deterministic polynomial time. <br /><br />Could you explain what properties this new algorithm has that the trivial algorithm does not have?<br />Anonymousnoreply@blogger.com