tag:blogger.com,1999:blog-3722233.post4806966094683791166..comments2019-09-16T22:22:57.835-04:00Comments on Computational Complexity: do we ever only care about the decision problem? I know of only one case of thatLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger11125tag:blogger.com,1999:blog-3722233.post-13516588144396287862019-02-12T07:24:37.037-05:002019-02-12T07:24:37.037-05:00In algorithmic graph theory, there are algorithms ...In algorithmic graph theory, there are algorithms for solving problems on special graph classes, as bipartite graphs, for example. For using such algorithms in practice one should first check whether the graph indeed belongs to the desired graph class, which is a decision problem.<br /><br />I can also think on problem involving a budget or profit, for which you could solve a decision problem before taking some action. You would only do something if you have enough resources or would get at least some profit from it.Viníciushttps://www.blogger.com/profile/01496834062674029636noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-78318001945679788302019-01-24T17:52:26.139-05:002019-01-24T17:52:26.139-05:00In crypto applications, we care about decisional v...In crypto applications, we care about decisional versions of problems all the time...Jonathan Katzhttps://www.blogger.com/profile/07362776979218585818noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-8391425777105707182019-01-21T07:20:48.646-05:002019-01-21T07:20:48.646-05:00Instead of talking about polynomial identity testi...Instead of talking about polynomial identity testing or word problems, it might be simpler to just talk about evaluation of canonical binary relations, like a partial order relation, or some equivalence relation. The decision problem is interesting for those cases, simply because those relations evaluate to true or false (for two given elements).<br /><br />The canonization is a bit different, since here a deterministic answer is of interest, but the answer is not restricted to true or false. The reduction of a search problem to a decision problem gives us such a deterministic answer, even so a nondeterministic answer would have been perfectly fine for that case. In fact, if we accept this "deterministic answer" property and restrict attention to partial functions, then we just get the PF^NP complexity class (of partial functions), which is not more complicated than the corresponding Δ^NP complexity class (of decision problems). This even gives us a nice example where Cook ("Turing") reductions are more appropriate than Karp ("many-one") reductions.<br /><br />This also helps to understand the feeling that "its cleaner mathematically to look at the decision problem", since a decision problem always has a deterministic answer, while getting a deterministic answer for a non-deterministic problem (with many valid answers) somehow feels wrong. Contemplating "canonization" can help to appreciate how getting a deterministic answer still fits together with multiple valid answers.Jakitohttps://www.blogger.com/profile/08235089048981338795noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-57343025347772969832019-01-16T07:19:35.742-05:002019-01-16T07:19:35.742-05:00By "we", I just meant the actual applica...By "we", I just meant the actual applications for which Graph Isom programs like bliss, conauto nauty, saucy, Traces, ... have been used, that "I" was aware of. These are things like explicitly generating all different small instances of some mathematical structures, counting the number of instances of some mathematical structure for given "rather small" parameters limiting the size of the structures, looking up biological or chemical structures in databases, ...<br /><br />Both <a href="https://en.wikipedia.org/wiki/Graph_isomorphism_problem#Applications" rel="nofollow">wikipedia</a> and <a href="https://math.stackexchange.com/questions/120408/what-are-the-applications-of-the-isomorphic-graphs" rel="nofollow">MSE</a> try to describe the typical applications of graph isomorphism. I like the perturbative expansion of Feynman's path integral application (since it shows why one wants to list all small instances of some mathematical structure), but I didn't spot a clear application of graph automorphism in those lists yet.<br /><br />In all those applications, canonization is what one is interested in, instead of an actual isomorphism. But since conauto and saucy only compute the automorphism group without offering canonization functionality, this cannot be the whole truth. I just tried looking at the conauto and saucy home pages to learn more about applications of graph automorphism. Let me just quote from saucy: "Many computational tools have recently begun to benefit from the use of the symmetry inherent in the tasks they solve, and use general-purpose graph symmetry tools to uncover this symmetry. Common applications include organic chemistry, constraint solvers, logistics, optimization, bio-informatics, and finite group theory."<br />Jakitohttps://www.blogger.com/profile/08235089048981338795noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1327787528726052732019-01-15T20:04:09.094-05:002019-01-15T20:04:09.094-05:00You bring up two good questions, maybe three
1) ar...You bring up two good questions, maybe three<br />1) are there people in the real world who care about Graph Isom?<br />2) If so, do they care about the actual isom?<br />3) ``we are normally not interested in the isom itself'' - who is ``we''GASARCHhttps://www.blogger.com/profile/03615736448441925334noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-52961343066616242602019-01-15T19:55:04.918-05:002019-01-15T19:55:04.918-05:00How about the word problem for a free algebra (NP-...How about the word problem for a free algebra (NP-complete for inverse rings, for example), polynomial identity testing ((1+x)^n)=1+x^n mod n iff n is prime, for example), or graph isomorphism testing. At least we are normally not interested in the isomorphism itself for graph isomorphism, even so we would prefer to get a canonical labeling instead of just yes/no, so that we can quickly lookup our graph, or throw-out duplicates.Jakitohttps://www.blogger.com/profile/08235089048981338795noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-41513787112287271872019-01-15T18:32:05.874-05:002019-01-15T18:32:05.874-05:00Fixed, thanksFixed, thanksGASARCHhttps://www.blogger.com/profile/03615736448441925334noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-3469503926776507212019-01-15T17:57:55.014-05:002019-01-15T17:57:55.014-05:00For (2), you must have a typo; you must mean "...For (2), you must have a typo; you must mean "How far apart ...?"Jim Hefferonhttps://www.blogger.com/profile/09292836035665054384noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-2841683951073306852019-01-15T16:42:42.091-05:002019-01-15T16:42:42.091-05:00Hi Bill,
Here's a symbol for you to use in yo...Hi Bill,<br /><br />Here's a symbol for you to use in your post: ≤Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-78553341460643299892019-01-15T16:03:11.138-05:002019-01-15T16:03:11.138-05:00In random CSP (say random $k$-SAT) there is a rang...In random CSP (say random $k$-SAT) there is a range of probabilities where we know that with high probability a satisfying assignment exists, but it's generally conjectured that finding one is hard.<br /><br />Your example isn't good, since for the specific numbers you give, just pick a vertex, throw away the smaller of neighbours and non-neighbours, repeat $2k-1$ steps, gives a $k$-clique or $k$-independent set in $O(k2^{2k})$-time. And something like this is true for any number we can prove is at least $R(k)$. (David Conlon's proof, I think, can be made into an algorithm)<br /><br />But, even if you assume $R(k)\le 3.99^k$, we don't know any algorithm which works fast on a graph with $3.99^k$ vertices.Petehttps://www.blogger.com/profile/02123359695496629332noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-79647523610450242492019-01-15T13:14:22.108-05:002019-01-15T13:14:22.108-05:00I can come up with cases in mathematical biology w...I can come up with cases in mathematical biology where you are studying genetic regulatory networks and looking for specific subgraphs that are provably NP, where I wouldn't care really about where the subgraph exists, but simply that it exists, since it's existence tells me a lot about switching pathways for gene expression.kjrosehttps://www.blogger.com/profile/18327862455935247816noreply@blogger.com