Timeline for Computational complexity of sizes and number of orbits of a group acting on a set
Current License: CC BY-SA 4.0
20 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 31, 2019 at 4:47 | answer | added | Joshua Grochow | timeline score: 1 | |
| Aug 22, 2019 at 18:01 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Apr 24, 2019 at 21:20 | review | Close votes | |||
| Apr 25, 2019 at 18:50 | |||||
| Apr 24, 2019 at 18:00 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Dec 25, 2018 at 17:02 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Nov 25, 2018 at 17:01 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Oct 27, 2018 at 8:15 | comment | added | Axel Dahlberg | @AndreasBlass I am not asking what the complexity of Problem 1 is in general. I am asking if #P-Completeness of Problem 2 IMPLIES #P-Hardness of Problem 1. A YES to this question would mean that for any such sequences of sets and any group action on them for which Problem 2 is #P-Complete, also Problem 1 is #P-Hard. A NO to this question would man that there is at least one case where Problem 2 is #P-Complete but Problem 1 is not #P-Hard. Could you let me know what makes this unclear? | |
| Oct 27, 2018 at 8:11 | comment | added | Axel Dahlberg | @KeithKearnes For which problem is the input size not clear? For problem 1 the input is a natural number and for problem 2 it's an element of one of the sets. | |
| Oct 26, 2018 at 20:49 | comment | added | Andreas Blass | The question assumes nothing about the cardinality of $X_n$. Without some such assumption Problem~1 can't be solved algorithmically even when $G$ is the trivial group. A comment on Keith Kearnes's answer suggests that maybe $X_n$ was intended to have cardinality $n$, but the actual question mentions super-polynomial size. So I'm voting to close as unclear. | |
| Oct 26, 2018 at 16:54 | comment | added | Keith Kearnes | @AxelDahlberg: It is still not clear how the problem size is measured. | |
| Oct 26, 2018 at 16:33 | history | edited | Axel Dahlberg | CC BY-SA 4.0 |
added 95 characters in body
|
| Oct 26, 2018 at 16:26 | comment | added | Axel Dahlberg | @ChrisGodsil I've re-written the question, I hope it's more clear now. | |
| Oct 26, 2018 at 16:25 | history | edited | Axel Dahlberg | CC BY-SA 4.0 |
added 463 characters in body
|
| Oct 26, 2018 at 15:51 | comment | added | Chris Godsil | If you goiNg to discuss complexity, we need to know the size of the input. | |
| Oct 26, 2018 at 13:59 | comment | added | Axel Dahlberg | @ChrisGodsil If I would write "for a fixed group action.." would that be clearer or do you mean to specify in what form the group action is represented? What exactly are you looking for? For example I assume that the action of a group element on an element of the set can be efficiently computed. | |
| Oct 26, 2018 at 13:37 | answer | added | Keith Kearnes | timeline score: 0 | |
| Oct 26, 2018 at 12:58 | comment | added | Chris Godsil | First you need to specify what you mean by “given a group action”. | |
| Oct 26, 2018 at 12:45 | review | Close votes | |||
| Nov 13, 2018 at 3:05 | |||||
| Oct 26, 2018 at 10:36 | answer | added | Felix | timeline score: 1 | |
| Oct 26, 2018 at 8:47 | history | asked | Axel Dahlberg | CC BY-SA 4.0 |