tag:blogger.com,1999:blog-3722233.post6482721495747819843..comments2024-03-04T02:59:26.350-06:00Comments on Computational Complexity: Problems we assume are hard. Are they? ALSO- revised version of Demaine-Gasarch-Hajiaghayi is posted!Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger6125tag:blogger.com,1999:blog-3722233.post-89689778959892596062023-03-25T10:00:22.914-05:002023-03-25T10:00:22.914-05:00Good question. While people have looked at randomi...Good question. While people have looked at randomized algorithms there have not been any that do better than subquadratic time. I have put a pointer to a 2-pager I wrote about known algorithms for 3SUM including randomized ones, next to the 3SUM entry above. The simple randomized one I describe might do better in practice. gasarchhttps://www.blogger.com/profile/03004932739846901628noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-19224797314424990952023-03-25T09:33:33.887-05:002023-03-25T09:33:33.887-05:00Naive question: For orthogonal vectors, and 3SUM, ...Naive question: For orthogonal vectors, and 3SUM, as well as 3XORSUM (3 SUM with d-dimensional F_2-vectors) have randomized algorithms been investigated? Is the randomized complexity (I am not an expert) known? Any references appreciated.Kodluhttps://www.blogger.com/profile/12418167413500125327noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-26362245868326358002023-03-14T07:13:17.047-05:002023-03-14T07:13:17.047-05:00There is a blog post of Thore Husfeldt: https://th...There is a blog post of Thore Husfeldt: https://thorehusfeldt.com/2017/12/05/np-is-wrong/ where he argues that the world without Cook-Levin is actually the more scientific viewpoint of hardness than the "mathematical curiosity" of NP.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-17685106233409073072023-03-14T03:58:58.829-05:002023-03-14T03:58:58.829-05:00Cook-Levin type theorem for example 8: ETR is comp...Cook-Levin type theorem for example 8: ETR is complete for the real version of NP. This was basically done by Blum, Shub and Smale for their algebraic model of computation (rather than the standard Turing machine model).Pascalhttps://www.blogger.com/profile/14201150679841329835noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-61267311196595529822023-03-13T12:19:53.621-05:002023-03-13T12:19:53.621-05:00I have added to the post to address your issue.I have added to the post to address your issue.gasarchhttps://www.blogger.com/profile/03004932739846901628noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-81335869876280481042023-03-13T11:34:20.761-05:002023-03-13T11:34:20.761-05:00I don't understand what you mean by "a Co...I don't understand what you mean by "a Cook-Levin type theorem," so I totally miss the point of your post. <br /><br />As an example, consider your fifth item. You mention that in the FPT world, weighted-SAT-k is W[1]-complete, and other problems equivalent to it are also called W[1]-complete. W[1]-complete problems are thought not to belong to FPT, and there is a hierarchy W[t] above W[1]. How is that different from the NP-completeness world, with the correspondence P ↔ FTP ; NP ↔ W[1] ; Polynomial hierarchy ↔ W[t] hierarchy?B.noreply@blogger.com