tag:blogger.com,1999:blog-3722233.post8980814517027039027..comments2023-02-01T14:18:10.414-06:00Comments on Computational Complexity: The Wikipedia Entry on NP-Intermediary Problems lists one of mine! I'm not bragging about it.Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger5125tag:blogger.com,1999:blog-3722233.post-45764780486250281262020-01-06T20:38:09.944-06:002020-01-06T20:38:09.944-06:00Thnaks, I added a comment about that.Thnaks, I added a comment about that.GASARCHhttps://www.blogger.com/profile/03615736448441925334noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-26923940974826145602020-01-06T18:03:23.428-06:002020-01-06T18:03:23.428-06:00Graph isomorphism problem is in the Graph algorith...Graph isomorphism problem is in the Graph algorithm sectionAnonymoushttps://www.blogger.com/profile/11949441880455865523noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-45726217490622188942020-01-06T13:13:21.517-06:002020-01-06T13:13:21.517-06:00Weighted graph isomorphism is equivalent to matrix...Weighted graph isomorphism is equivalent to matrix permutation problem. Mathematicians have not been able to solve this problem for more than 100 years. (When were matrices invented?) <br /><br />It is a fallacy to think that mathematicians were not interested in fast algorithm before the dawn of computers. In fact, fast algorithms were more important before computers since people had to calculate everything on paper. I recall reading somewhere that before Reimann formulated his now famous conjecture, he invented a fast approach for calculating the zeros of the zeta function. Can somebody elaborate on this point? I am not an expert.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-30953298811315704402020-01-06T08:16:22.300-06:002020-01-06T08:16:22.300-06:00I think Wikipedia's criteria mainly consist of...I think Wikipedia's criteria mainly consist of whether an editor ever bothered to add a problem to the list. I've taken an interest in related problems that look like good candidates for the list:<br /><br />Nash equilibrium computation, which is likely to be harder than winner determination in parity games (which is on the list despite being at severe risk of having a poly-time algorithm, since it's got a quasi-poly-time algorithm). NASH has no known subexponential algorithm and is still has the guarantee of not being NP-hard unless NP equals co-NP.<br /><br />Indeed, any seemingly-hard "total search" problem should qualify for the same reason. The <a href="https://en.wikipedia.org/wiki/TFNP" rel="nofollow">wikipedia page on TFNP</a> has a nice explanation (I did not write it!) FACTORING is arguably the most important such problem.<br /><br />The necklace-splitting problem is a strong candidate, since it's a total search problem with a <a href="https://en.wikipedia.org/wiki/Necklace_splitting_problem" rel="nofollow">wikipedia page</a> and is at least as hard as FACTORING (unlike NASH, which has not been successfully compared with FACTORING).<br /><br />Ladner's theorem still wins w.r.t. its criterion for "NP-intermediate" - it just requires P not equals NP, but the above total search problems need NP not equal to co-NP. In turn, the above problems come out ahead of graph isomorphism - as you've noted its NP-hardness merely collapses PH to the second level.Paul Goldberghttps://www.blogger.com/profile/10952445127830395305noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-65245977461480086032020-01-06T00:29:39.578-06:002020-01-06T00:29:39.578-06:00https://jeremykun.com/2015/11/12/a-quasipolynomial...https://jeremykun.com/2015/11/12/a-quasipolynomial-time-algorithm-for-graph-isomorphism-the-details/Anonymoushttps://www.blogger.com/profile/11067659793463483481noreply@blogger.com