Timeline for complexity of counting homomorphisms
Current License: CC BY-SA 2.5
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 2, 2010 at 12:55 | comment | added | Eric Rowell | I like this idea Bruce. I have wondered how one might randomize the obvious (exponential) algorithm that tests all $n$-tuples from $H$ against the defining relations of $G_L$. Maybe something like this would work. | |
| Jun 2, 2010 at 6:59 | comment | added | Bruce Westbury | You can embellish this by using the peripheral structure. That is, a knot group comes with a pair of commuting elements (up to conjugacy). Then choose a pair of commuting elements in $G$ and count homomorphisms sending the first pair to the second pair. My naive guess is that your questions will have similar answers in this context? | |
| Jun 1, 2010 at 18:09 | vote | accept | Eric Rowell | ||
| Jun 1, 2010 at 17:11 | answer | added | Ian Agol | timeline score: 3 | |
| May 31, 2010 at 16:44 | comment | added | Eric Rowell | edited to clarify. | |
| May 31, 2010 at 16:43 | history | edited | Eric Rowell | CC BY-SA 2.5 |
added 61 characters in body
|
| May 31, 2010 at 16:21 | comment | added | Roland Bacher | Sorry, the answer is yes for finitely presented groups. | |
| May 31, 2010 at 16:20 | comment | added | Roland Bacher | I guess you want polynomial time with respect of the logarithm of $\sharp(H)$? (The answer is trivially yes otherwise.) | |
| May 31, 2010 at 16:17 | history | asked | Eric Rowell | CC BY-SA 2.5 |