tag:blogger.com,1999:blog-3722233.post2727898493587029341..comments2019-01-20T08:19:16.834-05:00Comments on Computational Complexity: Search versus DecisionLance Fortnowhttps://plus.google.com/101693130490639305932noreply@blogger.comBlogger6125tag:blogger.com,1999:blog-3722233.post-24007961116119212612019-01-11T17:19:05.713-05:002019-01-11T17:19:05.713-05: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-10T13:46:48.859-05:002019-01-10T13:46:48.859-05: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-10T09:25:49.696-05:002019-01-10T09:25:49.696-05: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-09T17:36:26.218-05:002019-01-09T17:36:26.218-05: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-09T16:43:49.850-05:002019-01-09T16:43:49.850-05:00Thanks. Fixed.Thanks. Fixed.Lance Fortnowhttps://www.blogger.com/profile/06752030912874378610noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-82120218598156051902019-01-09T16:15:52.324-05:002019-01-09T16:15:52.324-05: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