Timeline for Computational complexity of sizes and number of orbits of a group acting on a set
Current License: CC BY-SA 4.0
2 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 22, 2020 at 10:40 | comment | added | Axel Dahlberg | Hi @Joshua! Thanks for your comments! One of the problems I was considering was also a graph problem, however in this case equivalence is under the action of "local complementation". In arxiv.org/abs/1907.08024 we showed that computing the size of such orbits is #P-Complete, however it is unclear how hard it is to count the number of orbits. I agree with you that since the problem only has an integer as input, it might be unlikely that this would also be #P-Complete. | |
| Oct 31, 2019 at 4:47 | history | answered | Joshua Grochow | CC BY-SA 4.0 |