tag:blogger.com,1999:blog-3722233.post4377715714707085161..comments2024-10-03T16:28:40.297-05:00Comments on Computational Complexity: From Homework Solution to Research PaperLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger5125tag:blogger.com,1999:blog-3722233.post-603071101311753072014-11-26T09:12:14.284-06:002014-11-26T09:12:14.284-06:00Hi Lance! It is easy to transform a finite set A o...Hi Lance! It is easy to transform a finite set A of integers into a Turing machine which decides these elements when they belong to A. Suppose we already have this Turing Machine M for some set A. Then, checking if some element x is the minimum in A would be equivalent to check if x is the minimum element which accepts M. I found this circunstance fascinating, because in the second case we could prove that x is the minimum in less than |A| steps. We already know that |A| - 1 is the lower bound to find the minimum of an integer set. However, when we change to this other model the order could change in relation to the size of x and not of A. I guess this might not be possible, because the size of A could be exponential in relation to the bit-length of x. Besides, I suspect we could not polynomially relate the enconding of some M and x (inside of an interval) to A and x . I found this has a close relation to the P versus NP problem and I shared as a preprint. <br /><br />https://hal.archives-ouvertes.fr/hal-01087331<br /><br />I presented as a conjecture and shared my opinion about it. I want to share it to you. Maybe it could be interesting and not some naive issue.Anonymoushttps://www.blogger.com/profile/01550125963313485816noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-60760781518245633232014-11-18T04:31:58.590-06:002014-11-18T04:31:58.590-06:00Neither my university nor the Max Planck Society h...Neither my university nor the Max Planck Society have access to this article, so I just spent 20 British pounds of taxpayer money to learn that the trick is: Replace every "-1" in the -1/0/1-Permanent with a gadget of weight 3^n * n!.Anonymoushttps://www.blogger.com/profile/11313269007477104619noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-89110290370017356992014-11-13T13:38:46.802-06:002014-11-13T13:38:46.802-06:00You have a better memory than I do. I did a search...You have a better memory than I do. I did a search for Zanko before I wrote today's post but "Zanko" didn't match "Zankó". Sorry for the duplicate and hopefully those who are newer to my blog find this post interesting.Lance Fortnowhttps://www.blogger.com/profile/06752030912874378610noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-57884623920214908142014-11-13T13:28:41.831-06:002014-11-13T13:28:41.831-06:00This blog post is essentially a duplicate of a pre...This blog post is essentially a duplicate of a previous post, see: http://oldblog.computationalcomplexity.org/archive/2003_03_01_archive.html , in particular the entry from March 14, 2003.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-41981757950839699152014-11-13T10:47:31.962-06:002014-11-13T10:47:31.962-06:00I knew this paper but not the story behind it, tha...I knew this paper but not the story behind it, thanks!Anonymousnoreply@blogger.com