Timeline for Computational complexity of sizes and number of orbits of a group acting on a set
Current License: CC BY-SA 4.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 26, 2018 at 16:26 | comment | added | Axel Dahlberg | I've re-written the question, I hope it's more clear now. | |
| Oct 26, 2018 at 15:52 | comment | added | Axel Dahlberg | $X$ is not part of the input. For the problem counting the number of orbits the input is simply the number of vertices $n$ and $X$ is then the graphs on $n$ vertices. For deciding the size of an orbit the input is a graph (element of $X$). I can rewrite the question for the case where $X$ are graphs if that's clearer. | |
| Oct 26, 2018 at 15:00 | comment | added | Keith Kearnes | I mean: what is the input to your original problem about groups acting on sets? Is $X$ part of the input? If so, then $X$ cannot be exponentially large in terms of the input (it is part of the input). So what is the input? | |
| Oct 26, 2018 at 14:20 | comment | added | Axel Dahlberg | Sorry for being unclear. In the case of graphs, the input is the number of vertices. | |
| Oct 26, 2018 at 14:06 | comment | added | Keith Kearnes | What is the input? | |
| Oct 26, 2018 at 14:04 | comment | added | Axel Dahlberg | The size of the orbits can be exponentially large in the input of the problem. So even if finding the orbits can exponentially long time, deciding their size can still be in $P$. No $X$ is finite but exponentially large in the input of the problem. $X$ can for example be all graphs on a fixed number of vertices or all words of a certain length with entries from a finite alphabet. | |
| Oct 26, 2018 at 13:42 | history | edited | Keith Kearnes | CC BY-SA 4.0 |
added 59 characters in body
|
| Oct 26, 2018 at 13:39 | history | undeleted | Keith Kearnes | ||
| Oct 26, 2018 at 13:37 | history | deleted | Keith Kearnes | via Vote | |
| Oct 26, 2018 at 13:37 | history | answered | Keith Kearnes | CC BY-SA 4.0 |