tag:blogger.com,1999:blog-3722233.post85446468..comments2024-08-03T11:58:59.111-05:00Comments on Computational Complexity: Complexity Class of the Week: FactoringLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger5125tag:blogger.com,1999:blog-3722233.post-66185221553509636342022-12-21T22:52:00.250-06:002022-12-21T22:52:00.250-06:00Why is factoring in UP\cap coUP? Can you elaborate...Why is factoring in UP\cap coUP? Can you elaborate? There are many factors (witnesses).Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-3651532163368004592014-03-31T08:45:32.022-05:002014-03-31T08:45:32.022-05:00Thank you very much. Sometimes, it's better no...Thank you very much. Sometimes, it's better not to trust 100% percent in ourselves(the people who are not excellent scientists yet such as students of any kind or followers of this issue in general), because we don't have to know everything and we might be wrong in many cases, for that reason it's very good to have the chance of receive an answer of an expert like you. Thanks again. Frank Vegahttps://www.blogger.com/profile/15257641208909866601noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-11997604933576621382014-03-28T21:11:41.593-05:002014-03-28T21:11:41.593-05:00Yes, your definition is correct. US does can allow...Yes, your definition is correct. US does can allow 0, 2 or more accepting assignments if x is not in L. Lance Fortnowhttps://www.blogger.com/profile/06752030912874378610noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-31588473935364876242014-03-28T13:09:42.532-05:002014-03-28T13:09:42.532-05:00Hello Dr. Fortnow,
I have a doubt in the class UP...Hello Dr. Fortnow,<br /><br />I have a doubt in the class UP in which you surely could help me. I used the definition that I found in wikipedia about the UP class:<br /><br />if x in L , then there exists a unique certificate y with |y| = O(|x|c) such that A(x,y) = 1<br />if x isn't in L, there is no certificate y with |y| = O(|x|c) such that A(x,y) = 1<br /><br />The link is:http://en.wikipedia.org/wiki/UP_(complexity)<br /><br />I thought this definition was correct, even though wikipedia might have had errors in this topic. However, I used this definition on an informal presentation of this topic and this caused confusion with the US class, even though I refered all the time in terms of unique certifcate.<br /><br />Could you tell me if this definition is wrong, please?<br /><br />I would appreciate your help, because I really need it. Frank Vegahttps://www.blogger.com/profile/15257641208909866601noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-12924656978541271892013-08-06T00:35:47.019-05:002013-08-06T00:35:47.019-05:00Hi there,
I share a least two common facts with ...Hi there, <br /><br />I share a least two common facts with Pierre de Fermat, I am French and I am an amateur mathematician mostly working on number theory. <br />I have been to many of your interesting posts in this blog and I guess you are highly qualified to answer my simple questions. Two questions exactly :<br /><br />1. Apart from the cryptography catastrophe, would there be some benefits of factoring being as fast as multiplication ? Any other practical aspects ?<br /><br />2. What would You Do, personally if E.T. would give you a simple ultra fast factoring algorithm ?<br /><br />Thanks in advance for your time and answers ....<br />Eric PouhierAnonymoushttps://www.blogger.com/profile/12005749767583527357noreply@blogger.com