tag:blogger.com,1999:blog-3722233.post2727898493587029341..comments2021-09-21T04:14:03.225-05:00Comments on Computational Complexity: Search versus DecisionLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger10125tag:blogger.com,1999:blog-3722233.post-74332355992144288902019-02-06T04:20:08.519-06:002019-02-06T04:20:08.519-06:00Hmm. What I wrote isn't quite right, though a...Hmm. What I wrote isn't quite right, though admittedly late at night for me. A decider for group isomorphism obviously isn't a decider for CSP.<br /><br />I'll think more about it.NP Slaglehttps://www.blogger.com/profile/06322388966706601689noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-70998187365377981852019-02-05T04:11:07.679-06:002019-02-05T04:11:07.679-06:00Hey Josh,
I couldn't find an algorithm for gr...Hey Josh,<br /><br />I couldn't find an algorithm for group isomorphism. Can you provide a link?<br /><br />We might consider a group to be a set of ordered triples following the usual group rules (associativity, closure, unique identity, unique inverses, and so on), then think of the isomorphism as a constraint satisfaction instance on said triples. CSPs have search-to-decision reductions like SAT, right?<br /><br />Hope all is well,<br />NPSNP Slaglehttps://www.blogger.com/profile/06322388966706601689noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-30602526452920480762019-01-31T02:07:40.247-06:002019-01-31T02:07:40.247-06:00Search-to-decision for *group* isomorphism remains...Search-to-decision for *group* isomorphism remains an interesting open problem. Although search-to-decision for graph isomorphism has been known for a long time, and group isomorphism (in the multiplication/Cayley table model) is easier than graph isomorphism, we still don't know how to do a search-to-decision reduction for groups.Joshua Grochowhttp://www.cs.colorado.edu/~jgrochow/noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-36764416981475837082019-01-31T02:05:05.630-06:002019-01-31T02:05:05.630-06:00I don't think this is known assuming only P ne...I don't think this is known assuming only P neq NP, but Bellare & Goldwasser (SIAM J. Comput., 1994) showed that if EE neq NEE, then there are languages in NP for which search is harder than decision.Joshua Grochowhttp://www.cs.colorado.edu/~jgrochow/noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-24007961116119212612019-01-11T16:19:05.713-06:002019-01-11T16:19:05.713-06:00I've invented Quaternionic Optimization(Progra...I've invented Quaternionic Optimization(Programming)<br /><br />http://vixra.org/abs/1812.0174Yuly Shipilevskyhttps://www.blogger.com/profile/13699450530150796472noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-59233287908601823732019-01-10T12:46:48.859-06:002019-01-10T12:46:48.859-06:00Is it known if P \neq NP, then search is harder th...Is it known if P \neq NP, then search is harder than decision?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-50056535622415493602019-01-10T08:25:49.696-06:002019-01-10T08:25:49.696-06:00Only two notes:
* the factoring problem seems to ...Only two notes:<br /><br />* the factoring problem seems to revert to normality if you ask: "given an integer N does it have more than two factors?"<br /><br />* a search problem is equivalent to a decision problem of the form "Given an instance x and two certificates a,b; does there exist a solution between a and b"? (x,a,b can be simple integers, provided that an efficient decode/encode enumeration of the instances and certificates exists).<br /><br />So (perhaps) the focus could be switched ("normalized") to the difference between "Does there exist a solution between a and b?" and "Does there exist a solution?" (both decision problems)<br /><br />Marzio De Biasihttps://www.blogger.com/profile/18441670787376943932noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-40659770727497145162019-01-09T16:36:26.218-06:002019-01-09T16:36:26.218-06:00One step in reducing Graph Isomorphism search to n...One step in reducing Graph Isomorphism search to non-adaptive Graph Isomorphism decision: For each vertex u in G and v in H, make a new pair of graphs, G' and H', where G' is the same a G except with a newly added large clique attached to u, and H' is the same as H except with a newly added large clique attached to v. Then G' and H' will be isomorphic iff there is an isomorhpism between G and H that maps u to v. Unfortunately, there may be many isomorphisms between G and H, so these queries do not allow us to non-adaptively find an isomorphism between G and H.Isaac Grosofhttps://www.blogger.com/profile/07538387185987936824noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-25414180610406394912019-01-09T15:43:49.850-06:002019-01-09T15:43:49.850-06:00Thanks. Fixed.Thanks. Fixed.Lance Fortnowhttps://www.blogger.com/profile/06752030912874378610noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-82120218598156051902019-01-09T15:15:52.324-06:002019-01-09T15:15:52.324-06:00I think "If you have some oracle (magic black...I think "If you have some oracle (magic black box) that answered search questions, can you solve the decision problem efficiently?" should be "If you have some oracle (magic black box) that answered decision problem, can you solve the search questions efficiently?"AndrĂ© Luiz Barbosahttp://www.andrebarbosa.eti.brnoreply@blogger.com